题目：给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）。(N<=10000000，M<=100000)
解法：1.欧拉筛O(n)，数组近乎100KB；2.（我这题copy了数据范围肯定是有原因滴......）欧拉函数判断素数O(m log n)，m 比 n 小啊，可以分解质因数求欧拉函数。
2种写法我在这篇博文里都有写：【poj 2407】Relatives（数论--欧拉函数 模版题）
下面的代码是第一种方法的，
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=10000000;
8 int pr=0;
9 int prim[700000],isprime[N+10];
10
11 void get_prime()
12 {
13 memset(isprime,-1,sizeof(isprime));
14 isprime[1]=0;//
15 for (int i=2;i<=N;i++)
16 {
17 if (isprime[i]==-1) prim[++pr]=i;
18 for (int j=1;j<=pr && prim[j]*i<=N;j++)
19 {
20 isprime[prim[j]*i]=0;
21 if (i%prim[j]==0) break;
22 }
23 }
24 }
25 int main()
26 {
27 get_prime();
28 int n,m,x;
29 scanf("%d%d",&n,&m);
30 while (m--)
31 {
32 scanf("%d",&x);
33 if (isprime[x]==-1) printf("Yes\n");
34 else printf("No\n");
35 }
36 return 0;
37 }