全TLE (萌新）

vector_STL_ @ 2024-10-12 22:10:49

#include<bits/stdc++.h>
using namespace std;
#define int long long
bool f(int a){
    if(a<2){
        return false;
    }
    if(a==2){
        return true;
    }
    if(a%2==0){
        return false;
            }
    for(int i=3;i<=sqrt(a);i+=2){
        if(a%i==0){
            return false;
        }
    }
    return true;
}
vector<int>c;
signed main(){
    int a;
    cin>>a;
    for(int i=2;i<=a;i++){
        if(f(i)){
            c.push_back(i);
        }
    }
    int b;
    cin>>b;
    for(int i=0;i<b;i++){
        int d;
        cin>>d;
        cout<<c[d-1]<<"\n";
    }
}

by Mzh2012 @ 2024-10-12 22:14:02

@zch120526

#include<bits/stdc++.h>
//#pragma GCC optimize(3)

//cout<<fixed<<setprecision(2);

using namespace std;

bool prime[100000001];
int zhi[20000001], cnt;
void ols(int n){
    for(int i=2; i<=n; i++){
        if(!prime[i]) zhi[++cnt] = i ;
        for(int j=1;j<=cnt && i*zhi[j]<=n;j++){
            prime[i*zhi[j]] = 1 ;
            if(i%zhi[j]==0) break;
        } 
    }
    return;
}

int main(){
    int n,q;
    cin>>n>>q;
    ols(n);
    while(q--){
        int a;
        cin>>a;
        cout<<zhi[a]<<endl;
    }

    return 0;
}

by Transparent_fish @ 2024-10-12 22:15:26

qp

by Jean_Gunnhildr @ 2024-10-12 22:21:43

@zch120526

1. 暴力肯定过不了，埃氏筛 O(nlog{log{n}}) 也过不了，用欧拉筛
2. 输入要优化，用 快读 或 scanf 或 在 signed main(){ 下一行加上 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 注意， cin cout 解绑之后输出会在输入结束后再一起输出，且此时cin、cout不可与printf、scanf混用
3. 求关注

by Elysium_Guiwow @ 2024-10-17 08:04:31

@Alicezhou 埃氏筛能过，而且埃氏筛跑的比欧拉筛快

by Jean_Gunnhildr @ 2024-10-17 09:52:45

@Elysium_Guiwow 欧拉筛是线性的

by Elysium_Guiwow @ 2024-10-17 10:33:18

@Alicezhou 埃氏筛常数小测试结果