第一份代码是我从题解搬下来的欧拉筛

第二份代码是我从别人提交记录里面看到的和埃氏筛很像的方法

为了防止有抄题解嫌疑 附上我自己的AC记录

然而我的代码跑了5s

第一份：

/*本人本题已过 复制题解原因是研究两种做法复杂度差距*/

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
        	//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤。见原理
		}
	}
}

int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	GetPrime(n);
	while (q--)
	{
		int k;
		scanf("%d", &k);
		printf("%d\n", Prime[k]);
	}
	return 0;
}

用时3.46s

第二份：

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int M=1e8;
bitset<M+1> a;
int b[M/10];

int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.in","w",stdout);	
	int n,q,i,j,k=0;
	scanf("%d%d",&n,&q);
	a[1]=1;
	a[0]=1;
	i=2;
	b[++k]=i;
	for(j=i*i;j<=M;j+=i)
		a[j]=1;
	for(i=3;i<=M;i++)
	{
		if(a[i]==0)
		{
			b[++k]=i;
			if(i>10000) continue;
			for(j=i*i;j<=M;j+=2*i)
			{
				a[j]=1;
			}
		}
	}
	while(q--)
	{
		scanf("%d",&k);
		printf("%d\n",b[k]);
	}
	return 0;
}

用时2.28s

两种做法差距在哪里 为什么第二种会比第一种快？