有关素数的问题

1.判断一个数n是否为素数：直接枚举

for(int i=2;i*i<=n;i++) { if(n%i==0) flag=false; else flag=true; } 从2~sprt(n)判断能否被n整除，可以的话就不是素数。

2.线性素数筛：当需要判断的素数非常多的时候，要用素数筛将素数保存起来。

int n;//素数筛的范围 int res[100];//保存素数 int prim[100]={1,1,0};//判断是否为素数 for(int i=2;i<n;i++) { if(prim[i]) continue; res[cnt++]=i; for(int j=i;j*i<=n;j++) { prim[i*j]=1; } }