蓝桥杯算法入门第15讲-2：素数

在算法竞赛中，素数的考点有三个：

素数的判定

素数筛

质因数分解

素数的那些事

素数定义：只能被 1和自己整除的正整数。

素数是极为简单的概念，2000多年前在数学研究刚起步的年代，素数就已经得到了很多研究。

然而，素数到现在还有很多未解之谜。例如著名的哥德巴赫猜想，还没有得到最终证明，最好的结果仍然是陈景润于1966年做的“大偶数表为一个素数及一个不超过二个素数的乘积之和”，即“1+2”。

素数并不少，在[1,n]内的素数个数k：

n=1百万，k=78,498，n/k=12.8

n=1千万，k=664,579，n/k=15.1

n=1亿，k=5,761,455，n/k=17.4

关于素数，存在以下有趣的事实：

（1）素数的数量有无限多。

（2）素数的分布。随着整数的增大，素数的分布越来越稀疏；随机整数x是素数的概率是1/log x。

（3）对于任意正整数n，存在至少n个连续的正合数。

有大量关于素数的猜想，著名的有：

（1）波特兰猜想：对任意给定的正整数n > 1，存在一个素数p，使得n < p < 2n。1845 年约瑟・伯特兰提出了这个猜想，1850 年切比雪夫证明了这个猜想。

（2）孪生素数猜想：存在无穷多的形如p和p+2的素数对。尚未证明。张益唐于2013所证明的孪生素数猜想的一个弱化形式：存在无穷多个差小于7000万的素数对。根据张益唐的方法，数学界把这个差缩小到了246。

（3）素数等差数列猜想：对任意正整数n > 2，有一个由素数组成的长度为n的等差数列。尚未证明。

（4）哥德巴赫猜想：每个大于2的正偶数可以写成两个素数的和。尚未证明。

素数的判定

如何判断一个数n是不是素数？当n ≤ 1012时，最直接的方法是试除法：用[2, n-1]内的所有数去试着除n，如果都不能整除，就是素数。

容易发现，试除法可以优化，把[2, n-1]缩小到[2, sqrt(n)]。因为如果n不是素数，那么它肯定有一个小于等于sqrt(n)的因子。

sqrt(n)是n的平方根，微信公众号文章不能输出根号

经过这个优化后，试除法的计算复杂度是O(sqrt(n))，n ≤ 1012时够用。下面是代码。

intis_prime(long long n){ if(n <= 1) return0; //1不是素数 for(long long i=2; i <= sqrt(n); i++) if(n % i == 0) return0; //能整除，不是素数 return1; //是素数 }

试除法还可以继续优化。[2,sqrt(n)]可以继续缩小，如果提前算出[2,sqrt(n)]内的所有素数，那么用这些素数来除n就行了，因为[2,sqrt(n)]中的合数已经被素数除过了。

例题：孪生素数

https://www.lanqiao.cn/problems/1555/learning/

题目描述：编写程序求孪生素数（如果 n 和 n+2 都是素数，则称它们是孪生素数）。

输入描述：输入一 个正整数 m(1≤m≤100)。

输出描述：输出两个均不超过 m 的最大孪生素数(中间空一格)。

题解：素数判定的简单应用。

#include using namespace std; int is_prime(long long n){ if(n <= 1) return0; for(long long i=2; i <= sqrt(n); i++) if(n % i == 0) return0; return1; } int main{ int m; cin>>m; for(int i=m; i>=3; i--) if(is_prime(i)&&is_prime(i-2)) break; cout<

读者可能发现，前面的试除法判断的素数都不太大。如果数字很大，例如一个>1020的数字，用试除法判断需要试1010次，1秒算不完。竞赛题一般只给1秒的判题时间，超时。

大素数的判断是一个难题，没有很好的方法。

当>1016时，可以用一个称为Miller-Rabin素性测试的方法，它是一个概率方法，能在很大概率上确定一个数是否为素数。

素数筛

素数筛解决这个问题：给定正整数n，求2~n内所有的素数。

如果图简单，可以用上一节的素数判定方法，一个个地判断。不过这样计算量有点大，有没有更快的方法？

容易想到用“筛子”，把非素数筛掉，剩下的就是素数。例如用2去筛2~n内的数，一次可以把所有的偶数筛掉。

有两种素数筛： 埃氏筛、欧拉筛。

埃氏筛：的计算复杂度是 O(nlog2log2n)，相当好。

欧拉筛：复杂度是 O(n)，不可能更快了。

埃氏筛的编码简单，一般情况下也够用。

埃氏筛的操作很简单。下面以初始数列{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}为例，说明它的操作步骤。

(1)记录最小的素数2，然后筛掉2的倍数，得：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

(2)记录下一个素数3，然后筛掉3的倍数，得：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

(3)记录下一个素数5，然后筛掉5的倍数，得：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

继续以上步骤，直到结束。

下面是代码，其中visit[i]记录数i的状态，如果visit[i] = 1，表示它被筛掉了，不是素数。用prime[]存放素数，例如prime[1]=2，是第一个素数。

const intN = 1e7; //定义空间大小，1e7约10M intprime[N+1]; //存放素数，它记录visit[i] = 0的项 bool visit[N+1]; //visit[i] = 1表示i被筛掉，不是素数 intE_sieve(intn) { //埃氏筛，计算[2, n]内的素数 intk=0; //统计素数个数 for(inti=0; i<=n; i++) visit[i]= 0; //初始化 for(inti=2; i<=n; i++) { //从第一个素数2开始。可优化（1） if(!visit[i]) { prime[++k] = i; //存素数，prime[1]=2, prime[2]=3... for(intj=2*i; j<=n; j+=i)//i的倍数，都不是素数。可优化（2） visit[j] = 1; //标记为非素数，筛掉 } } returnk; //返回素数个数 }

上述代码有2处可以优化：

（1）第7行，用来做筛除的数2、3、5......等，最多到sqrt(n)就可以。例如，求n = 100以内的素数，用2、3、5、7筛就足够了。其原理和试除法一样：非素数k，必定可以被一个小于等于sqrt(n)的素数整除，被筛掉。

（2）for(int j=2*i; j<=n; j+=i) 中的j = 2*i优化为 j = i*i。例如i = 5时，2*5、3*5、4*5已经在前面i = 2, 3, 4的时候筛过了。

下面是优化后的代码。

intE_sieve(intn) { for(inti = 0; i <= n; i++) visit[i]= 0; for(inti = 2; i<=sqrt(n); i++) //筛掉非素数 if(!visit[i]) for(intj=i*i; j<=n; j+=i) visit[j] = 1; //标记为非素数 //下面记录素数 intk=0; //统计素数个数 for(inti = 2; i <= n; i++) if(!visit[i]) prime[++k] = i; returnk; //返回素数个数 }

上面介绍了埃氏筛，还有一种方法是欧拉筛，这里不做解释，因为欧拉筛很精妙，不太容易理解。有兴趣的读者请查阅资料，或者看《算法竞赛》439页：

例题：素数个数

https://www.luogu.com.cn/problem/P3912

题目描述：求 1,2,⋯,N 中素数的个数。

输入格式：一个整数N。N<10^8。

输出格式：一个整数，表示素数的个数。

题解：素数筛的模板题。

注意本题对空间的限制125MB。代码第5行的bool vis[N]用了100M，第4行的int prime[N/16]用了25M。

#include using namespacestd; const int N = 1e8; int prime[N/16]; //保存质数，为节约空间，可以适当减小 bool vis[N]; int E_sieve(int n) { for(int i = 0; i <= n; i++) vis[i]=0; for(int i = 2; i<=sqrt(n); i++) if(!vis[i]) for(int j=i*i; j<=n; j+=i) vis[j]=1; int k=0; for(int i=2;i<=n;i++) if(!vis[i]) prime[++k]=i; returnk; } int main{ int n; cin>>n; cout << E_sieve(n); return0; }

质因数分解

正整数n可以唯一地分解为有限个素数的乘积：n = p1c1p2c2...pmcm，其中ci都是正整数，pi都是素数且从小到大。

分解质因子的简单方法也是试除法。求n的质因子：

（1）求最小质因子p1。从小到大检查从2到sqrt(n)的所有数，如果它能整除n，就是最小质因子。然后连续用p1除n，目的是去掉n中的p1，此时n更新为较小的n1。

（2）再找n1的最小质因子。从小到大检查从p1到sqrt(n1)的所有数。从p1开始，是因为n1没有比p1小的素因子，而且n1的因子也是n的因子。

（3）继续步骤（2），直到结束。

最后，如果剩下一个大于1的数，那么它也是一个素数，是n的最大质因子。例如6119 = 29*211，找到29后，剩下的n1=211是一个素数，也是质因子。

例题：因数分解

https://www.luogu.com.cn/problem/B3871

问题描述：每个正整数都可以分解成素数的乘积，例如：6=2×3，20=22×5。现在，给定一个正整数，请按要求输出它的因数分解式。

输入：输入第一行，包含一个正整数N。2≤N≤1012。

输出：输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号*表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头^表示，且左右不空格。

题解：质因数分解的模板题。

代码

#include using namespace std; typedef long long ll; int main{ ll n; cin>>n; for (ll i=2; i<=sqrt(n); i++) { //注意n是变化的 ll cnt=0; // 记录质因数i的个数 if (n%i==0) { // i是质因数 while(n%i==0){ //把n中的i除尽 n/=i; //更新n cnt++; } if (cnt==1) cout<1) cout<<" * "; //如果不是最后一个质因数，输出乘号 } } if (n>1) cout<

习题

lanqiaoOJ：孪生素数487、等差素数列646、梅森素数721、组素数722、找素数730、素数环1556、找素数1558、连续素数的和1881、最大素数3185、小明的素数对3205、疑似素数3334、消除和值为素数的数字对17475、卓卓的非素数和17874、素数集奇遇18060、质数数目310、质数608、质数拆分809、纯质数1561、超级质数2382、质数日期3397、质数游戏4232、魔法阵的能量3366、阿坤老师切割年糕3971、阶乘分解4226、阶乘的约数和4247、程序的输出零8213、双子数17105、躲炮弹17123。返回搜狐，查看更多