欧拉筛法寻找素数与计算欧拉函数求和
- 一、欧拉函数
- 1.1定义
- 1.2性质
- 1.3唯一分解定理（算术基本定理）
- 二、Eratosthenes筛法寻找素数
- 三、欧拉筛法寻找素数
- 3.1算法代码
- 3.2算法分析
- 3.2.1时间复杂度分析（对合数进行不重复筛选）
- 3.2.2算法正确性分析（对合数进行完全筛选）
- 3.3与Eratosthenes法实际运行时间对比
- 四、欧拉筛法计算欧拉函数求和
- 4.1欧拉函数求和代码
- 4.2代码改进
- 4.2.1使用vector类型数组
- 4.2.2优化数组使用
- 参考文档
一、欧拉函数
1.1定义
1~n中与n互质的数的个数被称为欧拉函数（记作 phi[n]），例如1 ~ 6中与6互质的数有1，5，所以phi[6]=2。规定phi[1]=1。
1.2性质
- 设 m = m 1 m 2 m=m_{1}m_{2} m=m1m2，若 m 1 m_{1} m1与m的所有素因数都相同，则phi[m]= m 2 m_{2} m2×phi[ m 1 m_{1} m1]
- 设 m = m 1 m 2 m=m_{1}m_{2} m=m1m2，若 m 1 m_{1} m1与 m 2 m_{2} m2互质，则phi[m]=phi[ m 1 m_{1} m1]×phi[ m 2 m_{2} m2]
- 若m为素数，则phi[m]=m-1
1.3唯一分解定理（算术基本定理）
设整数a≥2，则a一定可以表示为素数的乘积，即 a = p 1 p 2 . . . p s a=p_{1}p_{2}...p_{s} a=p1p2...ps， p s p_{s} ps是素数。
二、Eratosthenes筛法寻找素数
Eratosthenes筛法寻找素数的原理及步骤为：
- 根据唯一分解定理可推论出：对于整数n，一定有素因数p< n \sqrt{n} n；
- 首先筛选出1~ N \sqrt{N} N范围内的素数，这些素数的整数倍一定是合数，除去这些合数外，剩下的就是1-N范围内的素数。
Eratosthenes筛法算法复杂度为O(NloglogN)，代码如下：
unsigned eratosthenes(unsigned upL)
{
unsigned isprime[upL + 1] = {0};
unsigned m = sqrt(upL + 0.5);
for(unsigned i = 2 ; i <= m; i++)
{
if(!isprime[i])
{
for(unsigned j = i * i; j <= upL; j+=i)
{
isprime[j] = 1;
}
}
}
return 0;
}
三、欧拉筛法寻找素数
3.1算法代码
欧拉筛法寻找素数算法复杂度为O(N)，相较于Eratosthenes筛法时间复杂度大幅度降低，但是也更难理解，先给出代码如下：
unsigned euler(unsigned upL)
{
unsigned n = 0;
unsigned prime[upL + 1] = {0}, isprime[upL + 1] = {0};
for(unsigned i = 2 ; i <= upL; i++)
{
if(!isprime[i]) prime[++n] = i;
for(unsigned j = 1; j <= n && i * prime[j] <= upL; j++)
{
isprime[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
return 0;
}
3.2算法分析
3.2.1时间复杂度分析（对合数进行不重复筛选）
欧拉筛法求解思路与Eratosthenes筛法类似，都为先筛选出素数与合数，然后根据欧拉函数性质求和。
代码中筛选素数与合数的部分使用双重循环，但不会对合数进行重复筛选，此处关键代码为if(i % prime[j] == 0) break;，分析如下：
- 如果i除以prime[j]等于0，则说明i的其中一个素因数为prime[j]，设i=prime[j] * a；
- 而此时若不跳出对j的循环继续执行，则j++，i * prime[j+1]=prime[j] * prime[j+1] * a，prime[j+1] * a大于i，在以后对i的循环中必会重复遇到此合数，所以在此时跳出循环，控制程序只对合数筛选一次；
- 举例说明，当i=4时，4%2==0时，如不跳出内层循环，则下一次内循环会标记4 * 3=12为合数，而之后当i=6时，6*2=12又会被重复标记。
3.2.2算法正确性分析（对合数进行完全筛选）
对合数筛选的过程中是否会漏掉合数，分析如下：
- 根据唯一分解定理，任一合数m必然可以表示为素因数乘积的形式，设其中最小的素因数为p，则m可以表示为m=p*q；
- 而q一定≥p，否则m的最小素因数就不是p，当i循环到q时，素因数p一定被添加至prime数组中，m被标记为合数。
3.3与Eratosthenes法实际运行时间对比
经过多次测试，Eratosthenes法约为1ms，而欧拉法约为2ms，运行截图如下：
实际与理论相悖的原因可能是：欧拉法在筛选合数的同时需要操作一个额外的存储素数数组，造成了一定的运行时间浪费。
四、欧拉筛法计算欧拉函数求和
4.1欧拉函数求和代码
欧拉筛法计算欧拉函数与欧拉筛法寻找素数算法一脉相承，主要是利用前文介绍的欧拉函数的性质，在寻找素数的同时计算欧拉函数，在掌握了欧拉筛法寻找素数算法后，会对本小节算法一目了然，代码如下：
unsigned euler_sum(unsigned upL)
{
unsigned n = 0;
unsigned phi[upL + 1] = {0}, prime[upL + 1] = {0}, isprime[upL + 1] = {0};
phi[1] = 1;
unsigned res = 0;
for(unsigned i = 2 ; i <= upL; i++)
{
if(!isprime[i]) prime[++n] = i, phi[i] = i - 1;
for(unsigned j = 1; j <= n && i * prime[j] <= upL; j++)
{
isprime[prime[j] * i] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
//cout<<i<<','<<phi[upL]<<endl;
}
//cout<<phi[upL]<<endl;
for(unsigned i = 1 ; i <= upL; i ++) res += phi[i];
return res;
}
欧拉筛法求解欧拉函数求和，算法复杂度同样为O(N)。
4.2代码改进
4.1节给出的代码中在栈空间上定义了phi, prime, isprime三个数组，当输入的数较大时，可能会由于栈内存溢出而无法正确运行，有两种方法进行改进，第一种是使用vector类型数组，第二种是改进代码，将prime, isprime两个数组合并为一个数组，下面分别进行介绍。
4.2.1使用vector类型数组
vector是C++标准库中的容器，在堆上分配内存，并且自动管理内存的分配和释放，确保不会发生内存泄漏，代码如下：
unsigned euler_sum(unsigned upL)
{
unsigned n = 0;
vector<unsigned> phi(upL + 1), prime(upL + 1), isprime(upL + 1);
phi[1] = 1;
unsigned res = 0;
for(unsigned i = 2 ; i <= upL; i++)
{
if(!isprime[i]) prime[++n] = i, phi[i] = i - 1;
for(unsigned j = 1; j <= n && i * prime[j] <= upL; j++)
{
isprime[prime[j] * i] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
//cout<<i<<','<<phi[upL]<<endl;
}
//cout<<phi[upL]<<endl;
for(unsigned i = 1 ; i <= upL; i ++) res += phi[i];
return res;
上述代码只在三个数组定义处进行更改，其余地方未变。
4.2.2优化数组使用
由于1~N范围内的素数个数一定小于N，那么可以将prime, isprime两个数组合并，代码如下：
unsigned euler_sum(unsigned upL)
{
unsigned n = 0;
unsigned phi[upL + 1] = {0}, prime[upL + 1] = {0};
phi[1] = 1;
unsigned res = 0;
for(unsigned i = 2 ; i <= upL; i++)
{
if(!prime[i]) prime[++n] = i, phi[i] = i - 1;
for(unsigned j = 1; j <= n && i * prime[j] <= upL; j++)
{
prime[prime[j] * i] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
//cout<<i<<','<<phi[upL]<<endl;
}
//cout<<phi[upL]<<endl;
for(unsigned i = 1 ; i <= upL; i ++) res += phi[i];
return res;
}
此算法可以显著降低内存占用，降低空间复杂度。
参考文档
初等数论（潘承洞 潘承彪）
C++程序设计竞赛真题实战特训教程
算法竞赛入门经典（第2版） (刘汝佳)
