定义：除了1和其本身，没有其他约数的数。测试：用n分别试除2到sqrt(n)的数，如果中间有一个能整除，即
为合数，否则即为素数
bool is_prime(int n)//判断n是否为素数，是素数返回1{ int i; bool flag = 1; for(i = 2; i <= sqrt(n); i++) { if(n % i == 0){ flag = 0; break; } } return flag;}
小范围内筛素数（数据不太大）：#define Max 1000int Prime[500];int q;void get_prime(){ q = -1; Prime[++q] = 2; Prime[1] = 3; int i; for(i = 5; i <= Max; i++){ for(j = 0;Prime[j]*Prime[j] <= i &&i%Prime[j] != 0; j++); if(Prime[j]*Prime[j] > i)Prime[++q] = i; }}
大范围内筛素数的普通筛法（很慢）：#define Max 1000000int Prime[500000];bool IsPrime[Max] = {1};int q;void get_prime(){ q = -1; int i,j; for(i = 2; i*i < Max; i++){ if(IsPrime[i] == 1){ for(j = i+i; j < Max; j += i){ IsPrime[j] = 0; } } } for(i = 2; i < Max; i++){ if(IsPrime[i] == 1) Prime[++q] = i; }}
大范围内素数的线性筛法（比普通筛法更快）
#define Max 1000000int Prime[500000];bool IsPrime[Max] = {1};int q;void get_prime(){ q = -1; int i,j; for(i = 2; i < Max; i++){ if(IsPrime[i] == 1) Prime[++q] = i; for(j = 0;j <= q && Prime[j] * i < Max; j++){ IsPrime[Prime[j] * i] = 0; if(i % Prime[j] == 0)break; } }}
求某一区间（a,b）内的素数
有时候我们碰到的问题是要求求出a b间的素数，而a又比较大，
这种情况下就可以用这种方法实现（a>2)注意：要先通过以上几种方法求出2到sqrt(a的最大取值)范围内
的素数存入Prime[].
int prime[500000];bool isprime[1000000];int qt;void get_prime1(int a,int b){ int i,j,k; for(i = 0; i <= b - a; i++) isprime[i] = 1; for(i = 0; Prime[i]*Prime[i] <= b && i <= q;i++){ k = a/Prime[i]; if (k*Prime[i] < a) k++; if (k <= 1) k++; while(k*Prime[i] <= b){ isprime[k*Prime[i] - a] = 0; k++; } } qt = -1; for(i = 0; i <= b - a; i++) { if(isprime[i] == 1) prime[++qt] = i + a; }}
