蓝桥杯算法提高VIP-Torry的困惑(提高型) （C++代码）

解题思路:

旨在构造一个素数数组，利用素数判断一个数是不是素数，
如果是，则补充到素数数组中，以此类推就可以快速地找到
n以内所有素数。

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int M=100001;
unsigned long long a[M]={0};
int main()
{
	int n;
	while(cin>>n)
	{
		a[0]=2,a[1]=3,a[2]=5,a[3]=7;  
		int t=4;
		for(int i=11;;i+=2)
		{
			if(n<4||t==n)
			break;
			int ok=1;
			for(int j=1;a[j]*a[j]<=i;j++) //这里没必要考虑素数数组中所有的数，a[j]<=sqrt(i)即可 
			{
				if(i%a[j]==0)
				{
					ok=0;
					break;
				}
			}
			if(ok)
			a[t++]=i;
		}
		unsigned long long sum=1;
		for(int i=0;i<n;i++)
		{
			sum*=a[i];
			sum%=50000;
		}
		cout<<sum<<endl;
	}
	return 0;
}