救命!0pts求调!!!

P3383 【模板】线性筛素数

Creeperawwman @ 2024-05-26 15:34:33

感觉思路没问题,是不是我遗漏了什么细节???

#include<bits/stdc++.h>
using namespace std;
int n, q;
bool num[100000010];
int Rank[6000000], cnt;
void EiPrime(int x) {
    num[0] = num [1] = 1;
    for (int i = 2; i * i <= x; i++) {
        if (num[i] == 0) {
            Rank[++cnt] = i;
            for (int j = 2; j * i <= x; j++) {
                num[j * i] = 1;
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &q);
    EiPrime(n);
    while (q--) {
        int t = 0;
        scanf("%d", &t);
        printf("%d\n", Rank[t]);
    }
    return 0;
}

by masonxiong @ 2024-05-26 15:43:06

@Creeperawwman 咱们看看数据范围,n\le10^9,你需要更加优秀的算法


by masonxiong @ 2024-05-26 15:46:57

@Creeperawwman 实在不会欧拉筛可以用 bitset 加速埃氏筛然后读入输出优化艹过去


by vinegarchen @ 2024-05-26 15:47:45

不是质数也要和前面的数去筛,因此筛的部分不能在if判断里面


by vinegarchen @ 2024-05-26 18:17:14

感觉缺了点细节,建议借鉴题解


|