素数题

涉及素数的目前遇到2种
1.计算有多少个素数。
用线性筛法。如洛谷题目P3912

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int large=1e9;
bool noprime[large];
int main(void)
{int sum=0,i,d;
int maxn;
scanf("%d",&maxn);
sum=maxn-1;
    for(i=2;i<=sqrt(maxn);i++)//这里注意用sqrt，不然依然tle，数学的精华呀
{
    if(noprime[i]==0)
    {//此处体现线性筛法
        for(d=2*i;d<=maxn;d=d+i){if(noprime[d]==0)sum--;noprime[d]=1;}
        }
}
    printf("%d",sum);

    return 0;
}

2.判断是否是素数 （洛谷题目P3383)
也可以用第一种方法，建一个素数表,如以下

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
//const int maxn=1e7;
int maxn;
bool prime[10000000];
int main(void)
{int i,d;
 int a,b,c;
    scanf("%d %d",&a,&b);
    maxn=a;
    memset(prime,1,sizeof(prime));
    prime[0]=0;prime[1]=0;
    for(i=2;i<=sqrt(maxn);i++)
    {if(prime[i]==0)continue;
        for(d=i+i;d<=maxn;d=d+i)
            {
                prime[d]=0;
            }
    }

    while(b--)
    {
        scanf("%d",&c);
        if(prime[c])printf("Yes\n");
        else printf("No\n");
    }


}

但是看了其他人的解法，还有更快的，就是遇到一个素数时，再去判断它。当范围比较大时，样例比较少时。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int m,n;
bool isp(int n)
{
    if(n==1||n==4) return false;
    if(n==2 || n==3) return true;
    if(n%6 != 1 && n%6 != 5) return false;
    int qt=sqrt(n);
    for(int i=5;i<=qt;i+=6)
    {
    	if((n%i)==0 || n%(i+2) == 0) return false;
    }
    return true;
}


int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        if(isp(tmp)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}