普通算法——欧拉筛

欧拉筛

思路：

• 对欧拉筛的实现，主要是依靠一个数组模拟的栈来实现，核心思路为用栈储存已经发现的素数

• 在之后的遍历中，即可以素数数组中的数为因数来筛出此素数的倍数

• 遍历是以当前的 $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;
}