埃氏筛法与欧拉筛的原理

关于合数一定有质因子的证明

另外注明，素数即质数

	一个合数n之所以为合数，就是因为除1和本身之外，还至少有一个不等于n的素因子p。
    
	所以，一个合数n，如果存在大于1的正整数m和素数p，使n=m*p,则p为n的素因子，若m为合数，
则重复以上步骤求其余的素因子，直到n分解为素因子的乘积。

	例如256=2*2*2*2*2*2*2*2,510510=2*3*5*7*11*13*17.

也正是因为所有的合数一定有质因子，所以埃氏筛法和欧拉筛才是正确的

埃氏筛法的原理

从2开始，当我们遍历到一个素数时，把所有该素数的倍数（自然是合数）都筛选出来，进行标记

欧拉筛的原理

注：本段有参考某位大佬的文章

传送门

埃氏筛法的缺陷 ：对于一个合数，有可能被筛多次。例如 30 = 2 * 15 = 3 * 10 = 5*6……那么如何确保
每个合数只被筛选一次呢？我们只要用它的最小质因子来筛选即可，这便是欧拉筛法。

所以欧拉筛是在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100;
int prime[maxn];
int visit[maxn];
int main(){
	int cnt=0;
    memset(visit,0,sizeof(visit));
    memset(prime, 0,sizeof(prime));
    for (int i = 2;i <= maxn; i++) {//打表测试一下 
        cout<<"当 i = "<<i<<"时"<<endl;
        if (!visit[i]) 
            prime[cnt++] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
        for (int j = 0; j <cnt&& i*prime[j] <= maxn; j++) {
            cout<<"  j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
            visit[i*prime[j]] = 1;
/*
解释一：
prime[j]是当前已经确定的素数，而i*prime[j]计算的该素数的倍数 
此前有一点疑惑， i是外层循环的控制变量，有可能轮到这个素数的时候，i已经>2、3、4、5。。。了
就没办法计算这个素数的 2、3、4、5。。。倍了，但是其实是这样的，如果该素数前有素数
那么其实这两个素数的倍数已经被标记为合数了， 作为（比prime[j]小的素数）的倍数被标记了 
解释二： 
我们之前做埃氏筛法的优化时就已经知道了，循环标记时j的下标应该从i*i开始，原因见《计算机考研机试指南 》P96 
而在这里，我们得到一个新的素数的时候，prime[j]是通过i赋值给它得到的，那么其实i*prime[j]的初始值就相当于i*i 
也因此i是不会小于prime[j]的，也即i>=prime[j] 永真 
i如果是素数，那么i=prime[j]的最大值
i如果是合数，那么i>prime[j]的最大值 
*/
            if (i % prime[j] == 0) break;
/*
j是从小到大的， 那么prime[j]也是从小到大的，prime[j]里面存的都是素数，那么i对prime[j]求余能除尽，说明prime[j]是i的质因子 
那么i对prime[j]求余，遇到的第一个能除尽的数就是i的最小质因子
*/
        }
    }
}

《计算机考研机试指南 》P96

以下是与本期主题无关的一个小知识

	在if(表达式){语句} 条件语句里，如果表达式值为真的话，刚执行花括号里的语句；
	若表达式为假，刚不执行。
    1. if(!i)
    	表达式为(false)假，等价于i==0;
    2. if(i)
    	表达式为(true)真，等价于i！=0。（可假设i=1）
    可以简单记为"假零 真一"(贾玲)