欧拉筛 全部都MLE了

P3383 【模板】线性筛素数

jam1270 @ 2024-04-20 22:54:14

全部都MLE了

#include<iostream>
#include<bits/stdc++.h>
using namespace std; 
    bool Isprime(int);
    vector<int> eluer_sieve(int m){

        vector<int> result;
        vector<bool> status(m+1,true);

    for(int i=2;i<=sqrt(m);i++){
        if(Isprime(i)){

            result.push_back(i);
            for(int j=0;j<result.size()&&result[j]*i>m;j++)
            {

            if(i%result[j]==0)
            break;
            status[result[j]*i]=false;
        }

        }
    }
    for(int l=sqrt(m)+1;l<=m;l++){
        if(status[l]==true)
        result.push_back(l);
    }
     return result;

}
bool Isprime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)
        return false;
    }
    return true;
}
vector<int> eluer_sieve(int);
int main(){
    vector<int> res;
    int m,q;

    cin>>m>>q;
    res=eluer_sieve(m);

    for(int i=1;i<=q;i++){
        int seek;
        cin>>seek;
        cout<<res[seek-1]<<endl;
    }

}

by Terrible @ 2024-04-20 23:02:04

@jam1270

你这是什么迷惑行为程序？你好好对照题解写一遍呀。

by User966827 @ 2024-04-21 11:52:24

#include<iostream>
using namespace std;
bool check[100000005];
int z[100000005];
int main()
{
    std::ios::sync_with_stdio(0);
    int n,q,cnt=0;
    check[1]=1;
    for(int i=2;i<=100000000;i++)
    {
        if(!check[i])
        {
            z[++cnt]=i;
        }
        for(int j=1;j<=cnt&&z[j]*i<=100000000;j++)
        {
            check[z[j]*i]=1;
            if(i%z[j]==0)
            {
                break;
            }
        }
    }
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        int x;
        cin>>x;
        cout<<z[x]<<"\n";
    }
    return 0;
}

@jam1270 你这代码好迷啊

by shimucheng @ 2024-06-16 21:52:18

【真】欧拉筛

|