1.P3383 【模板】线性筛素数

“最小质因数 × 最大因数(非自己) = 这个合数”

P3383 【模板】线性筛素数

线性筛素数原理

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示:i是素数
int Prime[5000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
    memset(isPrime, 1, sizeof(isPrime));
    //以“每个数都是素数”为初始状态,逐个删去
    isPrime[1] = 0;//1不是素数

    for(int i = 2; i <= n; i++)
    {
        if(isPrime[i])//没筛掉 
            Prime[++cnt] = i; //i成为下一个素数

        for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
        {
            //从Prime[1],即最小质数2开始,逐个枚举已知的质数,并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然,i肯定比Prime[j]大,因为Prime[j]是在i之前得出的
            isPrime[i*Prime[j]] = 0;

            if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
                break; //重要步骤。见原理
        }
    }
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    GetPrime(n);
    while (q--)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", Prime[k]);
    }
    return 0;
}

2.P3912 素数个数

P3912 素数个数
1 , 2 , , N 1,2,\cdots,N 1,2,,N中素数的个数。
要注意的是long long 所占用的内存比int 大的多,所以如果 M L E MLE MLE了可以尝试把long long换成int

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cout<<"# "<<x<<endl
const ll N=5800000;
const ll base=137;
const ll mod=2147483647;
const ll INF=1<<30;
bool isnotprime[100000000];//筛
ll prime[N]/*存数*/,cnt=0;
void getprime(ll n)
{
    //isnotprime[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!isnotprime[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j)
        {
            isnotprime[i*prime[j]]=1;
            if(!(i%prime[j]))
                break;
        }
    }
}
int main()
{
    ll n;
    scanf("%d",&n);
    getprime(n);
    printf("%d\n",cnt);
}

3. O n ( 2 / 3 ) / l o g n O(n^(2/3)/log n) On(2/3)/logn的洲阁筛

洲阁筛

4. O N 2 / 3 O(N^(2/3)) ON2/3的MEISSEL-LEHMER算法

MEISSEL-LEHMER算法