前置知识

正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。

由唯一分解定理可知，任意一个自然数i必然可以 i = a*b （a为i的最小质因子）
这里非常重要，为什么我必须要规定 a为c的最小质因子呢？，这里我们先记住

#include<iostream>
using namespace std;

const int maxn = 1e7 + 7;

int prime[maxn], cnt = 0;
bool vis[maxn];		//0表示是素数，1表示是合数

void get_prime(int n) {
   
	for (int i = 2; i <= n; i++) {
   		//这里直接跳过1
		if (!vis[i])
			prime[cnt++] = i;    //记录素数
		for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
   		//只筛小于n的数 //i * prime[j]在某种情况下可能越界，可用 i <= n / prime[j]
			vis[i * prime[j]] = true;
			if (i % prime[j] == 0)    //避免重复筛选
				break;
		}
	}
}
int main() {
   

	int n;
	cin >> n;

	get_prime(n);		//寻找小于n的素数

	for (int i = 0; i < cnt; i++) {
   
		cout << prime[i] << " ";
	}
	return 0;
}

这里prime[j] 就代表质数数组 2，3，5，7…
不难发现，每一轮循环 ，对于每一个prime[j] （质数），他只用了 i 值 一次，这里也是和埃氏筛法 不同的地方（埃氏筛法是 把每一个素数的 倍数在一个循环内标记完，标记出来的就不是素数）， 而欧拉筛法每次只标记每个质数的i倍，标记出来的就不是素数，这是欧拉筛法的大体方向。

细细思考，这两种方法似乎是一样的 ， 有点类似与 a * b 和 b * a 的感觉

但是真的是这样吗？

大家都知道， 埃氏筛***有重复标记，这是不可避免的，因为这个算法一下子标记了一个质数的 2，3，4，5，6…n倍，而就在这 2，3，4，5，6…n 这些数中，还可能分解出更小的质数，而这个更小的质数，在执行它的循环时，肯定标记过 从 2到n中的数，而到这次循环时又标记了一次，这种重复计算 极大的降低了效率，而且没有了优化的空间

比如 12 = 2*6 在 埃氏筛中， 第一轮 质数2 就已经把 12 给筛走了 但是12 = 3 *4 ，第二轮 质数 3 又筛选了一次

而欧拉筛呢 ，他是第一轮循环 把 记录的所有质数 的 2 倍给 筛出来， 筛出来的就不是素数，第二轮把记录的所有的质数 的 3倍筛出来，筛出来的就不是素数，第三轮把记录的所有质数的4倍筛出来，筛出来的就不是素数…
如果仅仅按照这个思路， 欧拉筛和埃氏筛一模一样，就是a * b 和b * a 的关系 。

所以欧拉筛的 精华来了

if(i % prime[j]==0) break

先告诉你它的作用，防止重复筛选。那为什么呢？

我们来看我们一开始说的内容
由唯一分解定理可知，任意一个自然数i必然可以 i = a*b （ i为c的最小质因子这里非常重要，为什么我必须要规定 a为c的最小质因子呢？
可能 i 还可以被写成 i = c *d 的形式 ，但我们只要 a * b
我们举个例子

12 = 2 * 6
12 = 3 * 4
当对12 进行筛选的时候 ，在 12 % 2 ==0 那么直接跳出循环，3没有机会再对12进行标记。