离开了家乡，你到达了数字之地，在这里数字2总感觉自己是自然数中最独特的一个，他只有一和它本身两个因数，为此它十分苦恼。为了不再寂寞，他建立了素数王国，他请求许多人帮他聚集所有n以内的子民，可效率太低了。这样下去直到老死也无法完成，现在就靠你来帮他实现愿望了。 你使用了最简素数线性筛法 这种魔法前提是如果一个数是素数，那么它的倍数一定不是素数。也就是极大缩小了枚举的量。你又注意到，32和23其实是一回事，所以只乘一次即可。 所以只用正在判断的数作为不动乘数，遍历之前找到的素数与之相乘，可以大大避免重复乘法。 开辟一个大数组用做素数的标记，1代表素数，0代表非素数。
#define max 100000 bool isp[max];开辟大数组用于存放素数
long long a[max],t=0;除零和一外先把所有数全假设为素数
memset(isp,1,sizeof(isp)); isp[0]=isp[1]=0;下面就从2开始找n以内所有素数 首先输入n 然后遍历2~n并用t来标记找到了第几个素数 如果我们用作素数标志的bool值为1则为素数 除去素数的倍数即将他们的bool值设为0
for(long long ii=2;ii<=n;ii++){ if(isp[ii]!=0){ a[t++]=ii; } for(long long jj=0;jj<t&&a[jj]*ii<n;jj++){ isp[a[jj]*ii]=0; } }此时，a[t-1]中已经存满了n以内的所有素数，你也完美的完成了素数国王的任务。 告别了素数国王，你朝着迷失之地进发，只为变得更加强大。却不知还有多少危险在等待着你。
转载于:https://www.cnblogs.com/Martrix-revolution/p/9623694.html
