线性筛素数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 bool not_prime[10000003];
 7 int main()
 8 {
 9     int n , m , t;
10     scanf("%d%d" , &n , &m);
11     not_prime[0] = not_prime[1] = 1;
12     for(int i = 2; i <= n; i++)
13     {
14         if(not_prime[i])
15             continue;
16         for(int j = i + i; j <= n; j += i)
17             not_prime[j] = 1;
18     }
19     for(int i = 1; i <= m; i++)
20     {
21         scanf("%d" , &t);
22         not_prime[t] ? printf("No\n") : printf("Yes\n");
23     }
24     return 0;
25 }