素数筛

当遇到要求1~n之间的素数时,最纯的方法是$n^2$的,稍微聪明点的是$n√n$的。
遇到$10^6$或者更大的数据时就挂了。
所以我们需要学习素数筛,可以在接近线性的时间内筛出素数。

这里我只说(会)最好背的一种筛法,复杂度为$O(nloglogn)$

代码很简洁,四行。
其中book[i]表示i是否不是素数(book[i]为1时表示i不是素数)

for(int i=2;i<=n;i++)
    if(!book[i])
        for(long long j=(long long)i*i;j<=n;j+=i)
            book[j]=1;

那个j最好是long long,不然容易爆。还有i*i需要用long long进行运算,不然也容易爆。

这个筛(至少)可以过$10^7$的数据(亲测)。

它运用的思想:

把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。
——度娘

例题

【模板】线性筛素数 LUOGU – 3383
传送门= ̄ω ̄=

题解:模板题。
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m;
bool book[10000005];
int main()
{
    scanf("%d%d",&n,&m),book[1]=1;
    for(int i=2;i<=n;i++)if(!book[i])for(LL j=(LL)i*i;j<=n;j+=i)book[j]=1;
    while(m--){scanf("%d",&n);if(book[n])printf("No\n");else printf("Yes\n");}
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *