欧拉筛法 为什么会RE

P3383 【模板】线性筛素数

Janguiham0319 @ 2024-11-17 15:56:49

#include<bits/stdc++.h>
using namespace std;
int cnt=0,Prime[1000001]; 
bool isPrime[100000001];
void GetPrime(int n) {
    memset(isPrime,1,sizeof(isPrime));
    isPrime[1]=0;

    for(int i=2; i<=n; i++) {
        if(isPrime[i]) {
            Prime[++cnt]=i;
        }
        for(int j=1;  j<=cnt&&i*Prime[j]<=n; j++) {
            //j是合数的最小质因数
            isPrime[i*Prime[j]]=0;
            //所以:
            if(i%isPrime[j]==0) {
                break;
            }
        }
    }
} 
int main() {
    int n,q,k;
    cin>>n>>q;
    GetPrime(n);
    while(q--) {
        cin>>k;
        cout<<Prime[k]<<endl;
    }
    return 0;
}

by imzfx_Square @ 2024-11-17 16:03:09

@Janguiham0319 要不试试把 Prime 数组开大点


by guanyue7109 @ 2024-11-21 17:31:37

@Janguiham0319 应该是i%prime[j]==0时再break


by Janguiham0319 @ 2024-11-21 21:26:21

@guanyue7109 老师你好我现在已经AC啦 不过还是很感谢老师


by KillElena @ 2024-12-07 15:53:01

@Janguiham0319咋解决的


|