东北小蟹蟹

[luogu p3383] 【模板】线性筛素数
题面传送门题目描述如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)输入格式第...
扫描右侧二维码阅读全文
01
2019/10

[luogu p3383] 【模板】线性筛素数

题面

传送门
题目描述

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

输入格式

第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数,即询问该数是否为质数。

输出格式

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

输入输出样例

输入 #1
100 5
2
3
4
91
97

输出 #1
Yes
Yes
No
No
Yes

说明/提示

时空限制: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。

分析

这题的解法都写在题目里了嘻嘻嘻(模板题不都是这样吗,你个大菜鸡(自言自语.gif
Of course,这题还可以用别的更优的素数筛法,比如Miller Rabin之类的,之后我会考虑写一篇文章具体总结一下。
但是这篇题解我们只考虑欧拉筛哈。

首先来看一看普通的做法:

for(int i=2;i<sqrt(n);i++)
    if(n%i==0)
        return false;
return true;

判断一个数需要
$\sqrt{n}$
的时间。那么判断m个数,最大值为n需要
$m\sqrt{n}$
然鹅,题目的玄学数据范围是:

对于30%的数据:N<=10000,M<=10000
对于100%的数据:N<=10000000,M<=100000

很明显,此方法可以过 30%的数据,对全部数据却无能为力。
所以要考虑新的筛法:欧拉筛(线性筛)发现好多算法的名称与欧拉有关,时间复杂度需要控制在O(n)的范围。
那么怎么做呢?首先先思考:埃筛到底怎么浪费的青春时间?
再来看一遍code:

for(int i=2;i<sqrt(n);i++)
    if(n%i==0)
        return false;
return true;

对于一个数没啥好说的,但对于那么多的数,每次都用i来判一遍???
所以我们可以考虑:把经过腥风血雨的素数筛法的素数book下来,把它收入自己的军备库,干掉另一些合数。
棒!
当然这个说法太不够科学了。筛选素数就像上了战场,我们换一种说法:(敌人:未知 死人:合数 军人:素数)
2开始,如果当前的数没有被任何军人大义灭亲所干掉,说明当前敌人为素数,是军人。大水冲了龙王庙!把它收入自己的军备库。
当然如果当前敌人死了,那没啥好说的,继续吧。
但是,无论是死的活的,都要用它来干一波敌人:把其的素数倍数统统干掉。(想想还是挺那啥的
好的,这就是欧拉筛的基本原理。懂了吗?你可能有一个点不懂:
为什么一定是素数倍数??这里我们要明白一点:
任何一个整数都可以表示为一个质数和一个合数的乘积
你想啊,如合数倍数一定在之前就被干掉了。(合数的非自身因数比他小,所以其倍数肯定已经被提前干掉了)
就像一个死了的人你还要去打他,这不浪费子弹吗。
我们自然希望用最小质因数来干敌人,这样干的方便顺手,不浪费子弹啊。
为表示放便,先上一波代码:

    for(int i=2;i<=n;i++)
    {
        if(isprime[i]) prime_num[thiscnt++]=i;
        for(int j=0;j<thiscnt&&i*prime_num[j]<=n;j++)
        {
            isprime[i*prime_num[j]]=false;
            if(!(i%prime_num[j])) break;
        }
    }

thiscnt代表了当前记录质数的最大下标,即军队的最后一名的编号。
机智如你,一定猜到prime_num就是军队啦。
细心如你,你又看到了上述代码中有一句:
if(!(i%prime_num[j])) break;
What's this?
前面说过,

我们自然希望用最小质因数来干敌人,这样干的方便顺手,不浪费子弹啊。

那么我们保证当前的军人是最小的呢?秘籍就藏在这句话里,这句话堪称是欧拉筛的精华。没了他,Hello,TLE.再明确一遍:
当前敌人:i*prime_num[j]
当前分派军人:prime_num[j]
用来干敌人的半死不活人:i
分析一下:
if(!(i%prime_num[j])) break;
如果这个条件成立:说明了prime_num[j]i的质因子,同时不难看出这个质因子是最小的。
Why?
你想啊,如果还有比prime_num[j]更小的质因子,早就被break掉了。况且质因子是从小到大枚举的。
同样的,i*prime_num[j]的最小质因子也是prime_num[j]。所以,这样是不会浪费子弹的。
但是,再往上走,因为i有了prime_num[j]这个最小质因子,i*prime_num[k](k>j)的最小质因子仍然是prime_num[j]
呀!这不就浪费子弹了!所以当这个条件成立是,马上break掉。

代码分析完毕,你可能有一个疑惑:
这个算法的时间复杂度真的是O(n)吗????

    for(int i=2;i<=n;i++)
    {
        if(isprime[i]) prime_num[thiscnt++]=i;
        for(int j=0;j<thiscnt&&i*prime_num[j]<=n;j++)
        {
            isprime[i*prime_num[j]]=false;
            if(!(i%prime_num[j])) break;
        }
    }

这可是两个for啊?
其实,不要看有几个for。这个算法已经保证了不会浪费任一子弹。
简单证明一下:
设合数$ C=Ap={A_1}{p_1} $ ($p$和$p_1$都是质数)则${p_1}|A$。(因为两个质数不会贡献因子)
当$i$枚举到$A_1$,并试图想要筛C时,被if(!(i%prime_num[j])) break;无情拒绝。
所以:这个复杂度确实是线性的。有点反常理?
但是你想,后面的数基本上没什么可以枚举了,存活者也所剩无几。也就是说:到了后期,基本不用干什么了。。。

代码

blah blah blah这么多,是时候上代码了:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool isprime[10000005];
int prime_num[1000001];
int n,thiscnt,m,tmp;
void prime()
{
    isprime[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(isprime[i]) prime_num[thiscnt++]=i;
        for(int j=0;j<thiscnt&&i*prime_num[j]<=n;j++)
        {
            isprime[i*prime_num[j]]=false;
            if(!(i%prime_num[j])) break;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(isprime,true,sizeof(isprime));
    prime();//其实从这里我们可以看到,这种算法运行一次便可以筛所有素数,相当于预处理,一劳永逸。
    while(m--)
    {
        scanf("%d",&tmp);
        printf("%s\n",isprime[tmp]?"Yes":"No");
    }
    return 0;
}

over.

Last modification:November 9th, 2019 at 04:02 pm
东北小蟹蟹已经穷的叮当都响不了啦!!qwq

Leave a Comment

One comment

  1. 东北小蟹蟹


    已成功观赏完东北小蟹蟹的文章,并打算油炸东北小蟹蟹。Sun Oct 06 2019 23:26:47 GMT+0800 (中国标准时间) test