WA求助

P3383 【模板】线性筛素数

XRUIX @ 2024-03-27 16:23:19

案例全错了，不知道哪的问题

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>  
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

bool* isPrime = new bool[100000005];
int mydata[6000010];

void GetPrime(int n) {

    memset(isPrime, 1, sizeof(isPrime));
    //1不是素数
    isPrime[1] = 0;

    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        //没筛掉
        if (isPrime[i]) {
            mydata[++cnt] = i;
        }

        //遍历已有素数
        for (int j = 1; j <= cnt && i * mydata[j] <= n; j++) {
            //i*data->at(j)为素数
            isPrime[i * mydata[j]] = 0;
            //保证线性
            if (i % mydata[j] == 0) {
                break;
            }
        }
    }
}

int main()
{

    int n, k;
    cin >> n >> k;

    GetPrime(n);

    int curr;
    while (k--) {
        scanf("%d", &curr);
        printf("%d\n", mydata[curr]);
    }

    return 0;
}

by wwwee @ 2024-04-06 10:55:47

#include<bits/stdc++.h>
using namespace std;
long long t,b[10000005],n,i,j,q=0,w;
bool a[100000005];
void zss(int x)
{
    int e=1;
    a[1]=1;
    for(i=2;i<=x;i++)
    {
        if(a[i]==0)
        {
            b[e]=i;
            e++;
        }
        for(j=1;j<e&&b[j]*i<=x;j++)
        {
            a[b[j]*i]=1;
            if(i%b[j]==0)break;
        }
    }   
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>w>>n;zss(w);
    for(i=1;i<=n;i++)
    {
        cin>>t;
        cout<<b[t]<<endl;
    }
    return 0;
}

你看看

|