全部RE，不理解

thehanged @ 2024-04-12 17:17:43

#include <iostream>
#include <bitset>
using namespace std;

const int N = 1e8 + 10, M = 1e6 + 10;
int primes[M], cnt;
bitset<N> st;;

// 线性筛
void get_primes_liner(int n){
    for(int i = 2; i <= n; ++ i){
        if(!st[i]) primes[++ cnt] = i;
        for(int j = 1; j <= cnt && primes[j] <= n / i; ++ j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

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

by L_zaa_L @ 2024-04-12 17:30:12

@thehanged 1e8 里面的素数大概在 1e7 左右，所以数组要开到 1e7。

by _____QWQ_____ @ 2024-04-12 17:36:22

数组开小了 @thehanged M要等于1e8+10

by thehanged @ 2024-04-12 17:55:53

@zaa 确实是，我算错了，应该是1e7左右

by thehanged @ 2024-04-12 18:02:11

@QWQ thank you

by canwen @ 2024-05-11 20:34:22

@zaa 5700000 个左右而已

只需要开到 5800000 就能 AC 了

#include<iostream>
using namespace std;
#define maxn 5800000
int zhishu[maxn];
bool pd[(int)1e8];
int main(){
    int n,t,q=0;
    cin >> n >> t;
    for(int i=2;i<=n;i++){
        if(pd[i]==false){
            zhishu[++q]=i;
        }
        for(int j=1;j<=q&&zhishu[j]*i<n;j++){
            pd[zhishu[j]*i]=true;
            if(i%zhishu[j]==0)break;
        }
    } 
    for(int i=1;i<=t;i++){
        int w;
        cin >> w;
        cout << zhishu[w] << endl;
    }
}