当前位置：网站首页>Template_ Euclidean sieve_ prime number

Template_ Euclidean sieve_ prime number

2022-07-18 13:20:00 【This question AC sleep again】

//
#include<bits/stdc++.h>
using namespace std;

const int N=1e8+9;
int prime[N+5];
bool judge[N+5];

void sieve()
{
    memset( prime,0,sizeof( prime ) );
    memset( judge,0,sizeof( judge ) );
    int i,j,cnt=1;

    for( i=2;i<N-5;i++ )
    {
        if( judge[i]==0 ) prime[cnt++]=i; 
        for( j=1;j<cnt && i<N/prime[j];j++ )
        {
            judge[i*prime[j]]=1;
            if( i%prime[j]==0 ) break;
        }
    } 
}

int main()
{
    sieve();
    int n,q,x;
    
    while( cin>>n>>q )
    {
        while( q-- )
        {
            scanf( "%d",&x );
            printf( "%d\n",prime[x] );
        }
    } 
    return 0;
}

原网站

版权声明
本文为[This question AC sleep again]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/199/202207160319302813.html