紫书 习题 10-17 UVa 11105 (筛法）

类似于素数筛的思想去做，不然暴力会超时而且还要判重

#include<cstdio>
#include<cstring>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123456;
int vis[MAXN];
vector<int> prime;
int f[MAXN];void init()
{memset(vis, -1, sizeof(vis));for(int i = 5; i < MAXN; i += 4)for(int j = 5; i * j < MAXN; j += 4){if(vis[i] == -1 && vis[j] == -1) vis[i * j] = 1;else vis[i * j] = 0;}int sum = 0;REP(i, 1, MAXN){if(i % 4 == 1 && vis[i] == 1) sum++;f[i] = sum;}
}int main()
{init();int n;while(~scanf("%d", &n) && n)printf("%d %d\n", n, f[n]);return 0;
}