G08 筛质数 埃氏筛法 线性筛法

#include<bits/stdc++.h>
using namespace std;
const int N=1.6e7;
int p[N], pr;//p数组用于保存素数，pr为当前保存的素数个数 
bool v[N+10];//v[i]为1表示i是合数，为0表示i是素数 
void init()//素数打表（准备素数数组），每个合数的v只被其最小的质因数*i赋值为1 
{
    pr=0;memset(v,0,sizeof(v));
    for(int i=2;i<=N;i++)
    {
        if(v[i]==0) p[++pr]=i;
        
        for(int j=1;(j<=pr)&&(i*p[j]<=N);j++)
        {
            v[i*p[j]]=1;
            if(i%p[j]==0) break;
			/*i既然包含了p[j]，那么A1=i*p[j+1]、A2=i*p[j+2] …，
			A1、A2、A3…全都包含p[j]，这些数只愿意以 "v[？*p[j]]=1 "的形式被赋值*/
        }
    }
}
int main()
{
	init();
	int n,x;scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&x);
		printf("%d\n",p[x]);
	}
	return 0;
}
/*
素数个数： 
1-10:4
1-10^2:25
1-10^3:168
1-10^4:1229
1-10^5:9592
1-10^6:78498
1-10^7:664579
*/

G08 筛质数 埃氏筛法 线性筛法

#include<bits/stdc++.h>
using namespace std;
const int N=1.6e7;
int  p[N],pr;//p数组用于保存素数，pr为当前保存的素数个数 
bool v[N+10];//v[i]为1表示i是合数，为0表示i是素数 
void init()//素数打表（准备素数数组），每个合数的v只被其最小的质因数*i赋值为1 
{
    pr=0;memset(v,0,sizeof(v));
    for(int i=2;i<=N;i++)
    {
        if(v[i]==0) p[++pr]=i;
		    
        for(int j=1;(j<=pr)&& (i*p[j]<=N);j++)
        {
            v[i*p[j]]=1;
            if(i%p[j]==0) break;
			/*i既然包含了p[j]，那么A1=i*p[j+1]、A2=i*p[j+2] …，
			A1、A2、A3…全都包含p[j]，这些数只愿意以 "v[？*p[j]]=1 "的形式被赋值*/
        }
    }
}
int main()
{
	init();
	int n,x;scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&x);
		printf("%d\n",p[x]);
	}
	return 0;
}
/*
素数个数： 
1-10:4
1-10^2:25
1-10^3:168
1-10^4:1229
1-10^5:9592
1-10^6:78498
1-10^7:664579
*/