题目描述

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

输入格式

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

输出格式

输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

输入输出样例

输入 #1复制

100 52349197

输出 #1复制

YesYesNoNoYes

说明/提示

时空限制：500ms 128M

数据规模：

对于30%的数据：N<=10000，M<=10000

对于100%的数据：N<=10000000，M<=100000

样例说明：

N=100，说明接下来的询问数均不大于100且不小于1。

所以2、3、97为质数，4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,m;bool su(int a){ if(a==1){ return 0; } if(a==2||a==3){ return 1; } if(a%6!=1&&a%6!=5){ return 0; } int temp=sqrt(a); for(int i=5;i<=temp;i+=6){ if(a%i==0||a%(i+2)==0){ return 0; } } return 1;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x; scanf("%d",&x); if(su(x)){ printf("Yes\n"); } else{ printf("No\n"); } x=0; } return 0;}
           
          
         
        
       
      

　　

证明：令x≥1，将大于等于5的自然数表示如下： ······6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······ 可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。 根据以上规律，判断质数可以6个为单元快进，即将方法（2）循环中i++步长加大为6，加快判断速度。

 

知识来自 ：     。