看看我的为什么不对

P3383 【模板】线性筛素数

wangzaixi @ 2024-07-31 19:05:22

看看我的为什么不对(我写的是埃氏筛)

#include<bits/stdc++.h>
using namespace std;
int n,k,p,a[10000001],s=0;
bool zs(int x){
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    cin>>n>>p;
    for(int i=2;i<=n;i++){
        if(zs(i)){
            a[s]=i;
            s++;
        }
    }
    for(int i=0;i<p;i++){
        cin>>k;
        cout<<a[k-1]<<endl;
    }
}

by FLAMEs_ @ 2024-07-31 19:09:06

而且埃筛复杂度不对,n=10^8 的时候 O(n\log\log n) 的复杂度跑不动


by __O_v_O__ @ 2024-07-31 19:09:52

@wangzaixi 这不是埃氏筛啊,建议看看题解。


by Adchory @ 2024-07-31 19:13:58

@wangzaixi 可以考虑 Wheel Factorization 优化的埃式筛


by Steve_xh @ 2024-07-31 19:26:04

@wangzaixi 首先你这也不是埃氏筛啊,还有就是这题不能埃氏筛


|