欧拉筛及其扩展应用

首先我们先来回顾一下判定质数(试除法)：

 

 Tips:如果i*i爆int,则改为i<=x/i或i<=sqrt(x)。

下面讲欧拉筛之前我们先来看看朴素(筛法)求质数的案例吧！

如果只对一个整数进行素性判断，那么普通的判断素数的方法(复杂度为O(√n))也足够了，但如果对一系列数进行判断，那么复杂度太大，超时的可能性很大，这时就需要一个更高效的算法来求一定范围内的素数了，埃氏筛(复杂度为O(nloglogn))就可以很好地胜任这项工作。

埃氏筛的实现原理：

例如（打表）求0~1000以内的素数：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool vis[N];
int p[N];
int idx,n;
void get_primes(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i]){
			p[++idx]=i;//是素数，存起来 
			for(int j=i*i;j<=n;j+=i)//将素数i的倍数全部标记为合数
			vis[j]=true;
		}
	}
}
int main()
{
	cin>>n;//如输入1000即打印0~1000以内的素数 
	get_primes(n);
	for(int i=1;i<=idx;i++)
	cout<<p[i]<<",";
    return 0;
}

结果： 

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,

关键点解释：标记素数的倍数时,没有从j*2开始，从j*j开始，如果从j*m（m<j）开始，求得m的某个素因子时已经标记过，没必要再标记。 

例如,已知素数3，3*2=6,但6在i=2,2*3时就已经标记。

优化：如果数很大很大，那么就欧拉筛(复杂度O(n)故也称线性筛)来接替埃氏筛的这份工作了。

欧拉筛法是埃氏筛法的优化，非素数(合数)仅被最小素因子标记一次。在埃氏筛法中，对于一个非素数，它会被它的素因子标记多次(即重复了vis[j]=true)，例如,30=2*15=3*10=5*6，在得到素数2,3,5时均被标记一次，数大时更会标记很多次，做了很多无用功。

欧拉筛：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool vis[N];
int p[N];
int idx,n;
void get_primes(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
    	p[++idx]=i;
    	for(int j=1;j<=idx&&i*p[j]<=n;j++)
		{//取出每个素数，并把它的倍数 i*p[j] 标记为合数 
			vis[i*p[j]]=true;
			if(i%p[j]==0) break;
		}
	}
}
int main()
{
	cin>>n;//如输入1000即打印0~1000以内的素数 
	get_primes(n);
	for(int i=1;i<=idx;i++)
	cout<<p[i]<<",";
    return 0;
}

欧拉筛思想的核心是保证每个合数只被这个合数最小的质因子筛除，而且只筛一次。

关键点解释：break的原因->举个例子 ：i = 4 ，j = 1，p[j] = 2，4*2=8，如果不退出循环，接着4*3=12,那么12就会被3给筛除，但3并不是12的最小质因子，而12其实会在i=6,j=1时被2给筛除(6*2=12)。

难道欧拉筛只能用来求质数吗？答案是否定的！

欧拉筛除了可以用来求1~n的所有质数，还可以

求1~n的欧拉函数

求1~n的莫比乌斯函数

求1~n的约数个数和

求1~n的约数和

......

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

下面我们再来看怎么求欧拉函数！

首先我们得先知道什么是欧拉函数(定义