欧拉筛
思路：
-
对欧拉筛的实现，主要是依靠一个数组模拟的栈来实现，核心思路为用栈储存已经发现的素数
-
在之后的遍历中，即可以素数数组中的数为因数来筛出此素数的倍数
-
遍历是以当前的 i i i 值为基数，来乘当前素数数组中的数
-
而使欧拉筛快于埃氏筛的最关键的步骤则为
i%prime[j]==0 ; break;这一步使其筛除合数时，不会重复筛出同一个数如： 2 3 4 5 6 7 8 9 10 11 12 中
会先将2存进数组中，此时 i=2，数组中有2，所以筛去4，而此时2能被2整除，所以跳出循环
再将3存入数组，此时 i=3…
-
注意在循环条件时要加上
i * primes[j] <= N不然容易发生数组越界
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N = 500;
bool vis[N];
int prime[N];
int pos = 0;
int n;void Is_Prime(int p){vis[0] = vis[1] = false;for (int i = 2; i <= p; i++){if(vis[i])prime[++pos] = i;for (int j = 1; i * prime[j] <= p; j++){vis[i * prime[j]] = false;if(i % prime[j] == 0)break;//整除中断//条件i%p==0，保证合数只被最小质因子划掉//若i是质数，则最多枚举到自身中断//若i是合数，则最多枚举到自身的最小质数中断}}
}int main(){memset(vis, true, sizeof(vis));cin>>n;Is_Prime(n);for (int i = 1; i <= pos; i++)cout<<prime[i]<<" ";return 0;
}
