线性筛法求素数详解

 1 #include 
 2 #include 
 3 #include 
 4 
 5 const int MAX_N = 10000000 + 10;
 6 
 7 bool vis[MAX_N];
 8 int Prime[MAX_N >> 1];
 9 inline void GetPrime(int n) {
10     memset(vis, false, sizeof(vis));
11     vis[1] = true;
12     int cnt = 0;
13     for (int i = 2; i <= n; ++i) {
14         if (!vis[i]) Prime[++cnt] = i;
15         for (int j = 1; j <= cnt && i * Prime[j] <= n; ++j) {
16             vis[i * Prime[j]] = true;
17             if (i % Prime[j] == 0) break;
18         }
19     }
20 }
21 
22 int main() {
23     int n, m;
24     scanf("%d%d", &n, &m);
25     GetPrime(n);
26     while (m--) {
27         int x;
28         scanf("%d", &x);
29         if (!vis[x]) puts("Yes");
30         else puts("No");
31     }
32     return 0;
33 }