怎么判断一个数是素数？

常规的方法是枚举从2开始的数，看看是否能被整除。

但是，如果要判断的数很多的时候，那么效率会十分低下.。。。

一个优化的方法是不用判断比这个数小的所有数（到平方根位置），而是判断比他小的所有素数。

如果所有小于他的素数都不能将其整除，那么他就是素数。

那么如何快速得到小于他的素数?

有个Eratosthenes

把最后决定采用的写法放开头。。不是素数的标记为1

for(int i=2;i*i<=1000000;i++)        {    		if(!isprime[i])        for(int j=i;j*i<=1000000;j++)               isprime[i*j]=1;                   }

根据刘汝佳的书的代码如下：

可是当n为100万时候竟然直接停止工作！

#include
    
     using namespace std;const int MAXN=1000+10;int main(){	int n;	cin>>n;	int vis[MAXN],primer[MAXN],count=0;	memset(vis,0,sizeof(vis));	for(int i=2;i<=n;i++)	{		if(!vis[i]) 			primer[count++]=i;		//将素数存入		for(int j=i*i;j<=n;j+=i)	//标记是否是素数，如果不存入的话,直接判断vis[target]是否为0也可以。					vis[j]=1;				}	for(int i=0;i
    

判断一个数是否是两个素数的乘积。

多组数据不超过1000组，每组数据一行一个整数n(2 =< n <=1000000)。

n是否是两个素数的乘积，是输出Yes，不是输出No。

下面的写法是非素数标记为1

听队友的改进如下：

#include
    
     const int MAXN=1000000+10;bool vis[MAXN]={0};int main(){	int count=0;	 for(int i=2;i*i<=1000000;i++)      {          for(int j=i;j*i<=1000000;j++)             vis[i*j]=1;                 } 		int n;	while(~scanf("%d",&n))	{		bool ok=false;		for(int i=2;i * i <=n;i+=1)		{			if(vis[i]) continue;			int t=n / i;			if(t*i==n && !vis[t] )			{				ok=true;				break;			}		}		if(ok)			printf("Yes\n");		else			printf("No\n");	}}
    

FZU1563

可是在FZU这题直接TLE!搜题解得到如下写法

#include
    
     const int MAXN=1000000+10;const int INF=1000000;bool isprime[MAXN]={0};int prime[MAXN];int main(){	int pnum=0;	for(int i=2;i<=INF;i++)  	{  		if(!isprime[i]) prime[pnum++]=i;    		for(int j=0;j
     
      <=INF;j++)  		{  			isprime[prime[j]*i]=1;    			if(i%prime[j]==0) break;  		}  	} 	int n;	scanf("%d",&n);	while(n--)	{		int a,b;		int cnt=0;		scanf("%d%d",&a,&b);		for(int i=a;i<=b;i++)			if(isprime[i]==0)				cnt++;		printf("%d\n",cnt);	}}
     
    

最后改进如下：

#include
    
     const int MAXN=1000000+10;const int INF=1000000;bool isprime[MAXN]={0};int prime[MAXN];int main(){	 for(int i=2;i*i<=1000000;i++)        {    		if(!isprime[i])        for(int j=i;j*i<=1000000;j++)               isprime[i*j]=1;                   }  	int n;	scanf("%d",&n);	while(n--)	{		int a,b;		int cnt=0;		scanf("%d%d",&a,&b);		for(int i=a;i<=b;i++)			if(isprime[i]==0)				cnt++;		printf("%d\n",cnt);	}}