LightOJ 1336 Sigma Function(1--n中所有因子和为偶数的数字个数)

题目链接：
LightOJ 1336 Sigma Function
题意：
找到1–n中所有因子和为偶数的数字个数。n <= 1e12.
分析：
通过打表发现平方数和平方数的二倍的因子和是奇数。那就只要找小于等于n的平方数和平方数的二倍的个数就好了。
打表的程序：

const int MAX_N = 10010;int prime_cnt, total;
int prime[MAX_N], sum[MAX_N], Left[MAX_N];
bitset<MAX_N> bs;void GetPrime()
{prime_cnt = 0;bs.set();for(int i = 2; i < MAX_N; i++){if(bs[i]) prime[prime_cnt++] = i;for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; j++){bs[i * prime[j]] = 0;if(i % prime[j] == 0) break;}}
}bool Judge(int x)
{for(int i = 0; prime[i] * prime[i] <= x; i++){if(x % prime[i] == 0){int num = 0;while(x % prime[i] == 0){num++;x /= prime[i];} if(prime[i] != 2 && (num & 1)) return true; }}if(x > 2) return true;return false;
}int main()
{GetPrime();total = 0;for(int i = 1; i < MAX_N; i++){if(!Judge(i)) Left[total++] = i;;}for(int i = 0;  i < total; i++){ //Left数组存的就是因子和为奇数的数printf("%4d ", Left[i]);if((i + 1) % 10 == 0) printf("\n");}
}

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010;int T, cases = 0;
ll n;int main()
{scanf("%d", &T);while(T--){scanf("%lld", &n);ll num = 0;for(ll i = 1; i * i <= n; i++){num++;if( 2 * i * i <= n) num++;}printf("Case %d: %lld\n", ++cases, n - num);}return 0;
}