洛谷P3383题解

题目描述

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

输入输出格式

输入格式

第一行包含两个正整数$N,M$，分别表示查询的范围和查询的个数。
接下来$M$行每行包含一个$1 \leq num \leq N$的整数$num$，即询问该数是否为质数。

输出格式

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

INPUT & OUTPUT 's example

Input's eg #1

100 5
2
3
4
91
97

Output's eg #1

Yes
Yes
No
No
Yes

说明

时空限制：$500ms\; \& \;128M$
数据规模：
对于30%的数据：$N \leq 10000$，$M \leq 10000$
对于100%的数据：$N \leq 10000000$，$M \leq 100000$

样例说明：

$N=100$，说明接下来的询问数均不大于$100$且不小于$1$。
所以$2,3,97$为质数，$4,91$非质数。
故依次输出Yes、Yes、No、No、Yes。

分析

先来看一下素数的定义:

质数定义为在大于$1$的自然数中，除了$1$和它本身以外不再有其他因数。
————By 百度百科

所以就诞生了最简单的筛素数的方法：
我们对于传入的$N$从$2$枚举到$N-1$，每个数取模一下，从而判断是不是素数。

bool is_prime(int n){
    if(n==1)    return false;
    if(n==2)    return true;
    for(register int i=2;i<=n-1;i++){
        if(n%i==0)  return false;
    }
    return true;
}

这种做法的时间复杂度为$O(N)$,显然，当$N \geq 1e9$甚至更大的时候，肯定就会$TLE$到飞起。
本做法得分:$30QwQ$
qwq记录

通过几次尝试之后，我们可以发现，因数总是成对以$\sqrt{N}$为轴成轴对称，所以：
我们对于传入的$N$,只需从$2$枚举到$\sqrt{N}$即可。

bool is_prime(int n);{
    if(n==1)    return false;
    if(n==2)    return true;
    for(register int i=2;i<=sqrt(n);i++)
        if(n%i==0)  return false;
    return true;    
}

上述程序时间复杂度为$O(\sqrt{N})$，大大减少了程序的复杂度。
本做法得分：$100QwQ$
qwq记录

那么，还能够继续优化吗？

当然可以！

刚学$OI$的时候，唐只讲到优化$1$，sb的我就以为这是最快的了。
直到，看到了，某太阳：%3462^&sdh234>>>>dkfjlw
的一通哔哩哔哩筛法，嗯。。。。
证明：摘自质数判定方法。
证明：令$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$的相邻两侧。
所以，基于以上条件，我们假如要判定的数为$n$，则$n$必定是$6x-1$或$6x+1$的形式，对于循环中$6i-1，6i，6i+1,6i+2,6i+3,6i+4$其中如果$n$能被$6i，6i+2，6i+4$整除，则$n$至少得是一个偶数，
但是$6x-1$或$6x+1$的形式明显是一个奇数，故不成立；另外，如果$n$能被$6i+3$整除，则$n$至少能被$3$整除，
但是$6x$能被$3$整除，故$6x-1$或$6x+1$（即$n$）不可能被$3$整除，故不成立。综上，循环中只需要考虑$6i-1$和$6i+1$的情况
即循环的步长可以定为$6$，每次判断循环变量$k$和$k+2$的情况即可，代码如下:

bool is_prime(int n)
{
    if(n==1)    return false;
    if(n==2||n==3)  return true;
    if(n%6!=1&&n%6!=5)  return false;
    for(register int i=5;i*i<=n;i+=6)
        if(n%i==0||n%(i+2)==0)  return false;
    return true;
}

理论上述程序的时间复杂度约为$O(\frac{\sqrt{N}}{3})$。
本做法得分：当然是$100QwQ$
qwq记录

代码实现

/* Headers */
#include<cstdio>
#include<cctype>
#include<cmath>
/* define */
#define MAXN 100010
using namespace std;
namespace FastIO{
    const int BUFSIZE=(1<<20);
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }  
        return neg?-res:res;
    }
    inline void write(int x){
        if(x<0)x=-x,putchar('-');
        if(x>10)write(x/10);
        putchar(x%10+'0');
    }
    inline void space(int x){
        if(x==0)putchar(' ');
        else putchar('\n');
    }
} 
using namespace FastIO;
/* definitions */
int N,m,q;
/* functions */
bool is_prime(int n){
    if(n==1)    return false;
    if(n==2||n==3)  return true;
    if(n%6!=1&&n%6!=5)  return false;
    for(register int i=5;i*i<=n;i+=6)
        if(n%i==0||n%(i+2)==0)  return false;
    return true;
}
int main(int argc,char *argv[]){
    scanf("%d%d",&N,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&q);
        if(is_prime(q)){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

THE END