ToStar @ 2024-07-29 20:56:24

#include<cstdio>
#include<vector>
using namespace std;
bool notprime[(int)1e8+1000];
vector<int> prime;

int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    notprime[1] = 1;
    for (int i = 2; i <= n; i++){
        if(!notprime[i]){
            prime.push_back(i);
        }
        for (auto j : prime){
            if(i%j==0||i*j<=n)break;
            notprime[i * j] = 1;
        }
    }
    while (q--){
        int k;
        scanf("%d", &k);
        printf("%d\n", prime[k]);
    }
    return 0;
}

by zhanghengrui0502 @ 2024-07-29 21:11:07

我的代码:```cpp

include<bits/stdc++.h>

using namespace std; bool noprime[100000005]; int prime[1000005]; int main(){ int n,q,tot=0,x; cin>>n>>q; for(int i=2;i<=n;i++){ if(!noprime[i])prime[++tot]=i; for(int j=1;j<=tot&&prime[j]i<=n;j++){ noprime[prime[j]i]=true; if(i%prime[j]==0)break; } } while(q--){ cin>>x; cout<<prime[x]<<"\n"; } return 0; }

by zhanghengrui0502 @ 2024-07-29 21:11:59

我的代码：

#include<bits/stdc++.h>
using namespace std;
bool noprime[100000005];
int prime[1000005];
int main(){
    int n,q,tot=0,x;
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        if(!noprime[i])prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=n;j++){
            noprime[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
    while(q--){
        cin>>x;
        cout<<prime[x]<<"\n";
    }
    return 0; 
}

by zhanghengrui0502 @ 2024-07-29 21:12:22

第一个不算，打错了

by ToStar @ 2024-07-29 22:24:48

过了，问题出在欧拉筛的退出条件写早了

#include<iostream>
#include<vector>
using namespace std;
bool notprime[(int)1e8+1000];
vector<int> prime;
void getprime(int n){
    notprime[1] = 1;
    for (int i = 2; i <= n; i++){
        if(!notprime[i]){
            prime.push_back(i);
        }
        for (auto j : prime){
            if(i*j>=n)break;
            notprime[i * j] = 1;
            if(i%j==0)break;
        }
    }
    return ;
}
int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    getprime(n);
    while (q--){
        int k;
        scanf("%d", &k);
        printf("%d\n", prime[k-1]);
    }
    return 0;
}