算法篇——素数问题(看了就会）

大家好，欢迎来到IT知识分享网。

一.因数 素数 合数 

1.因数是可以整除一个数的整数，例如1，2，3，6可以整除6，那么这些除数就叫做被除数的因子。

2.素数也叫质数，指的是在大于1的自然数中，除了1和本身不在有其他因数的自然数。

例如 2 3 5 7 11，这些数字的因数都是由1和本身构成的。

3.合数是素数的反义词，是指除了1和本身两个因数外，至少还有1个因数。

例如 4 6 8 10 .这些数字的因数除了1和本身，还有其他的因数。

注意：1既不是素数也不是合数！！！

二.判断是否是素数的一般方法

现在给定一个数字n(n!=1&&n>1)，判断是否是素数，是的话返回“ture”,否则返回“false”。

按照素数的定义， 我们直接遍历循环因子。

我们先来写寻找合数 for循环的条件

for()循环里的三个参数分别是 (初始化 条件 迭代) 若满足条件则执行for括号内的语句。

若不满足，直接跳过for括号的语句。

 for(int i = 2;i<number;i++)

合数是除了1和本身外，还可以被其他的数整除。

我们剔除1和本身，遍历因子。所以我们从2开始， 循环到该数前一位。

bool isPrime(int number){ for(int i = 2;i<number;i++){ if(number % i == 0){ return false; } } return true; } 

Finall.不足

n>26500时，time超过1000ms;

为了寻找符合条件的因子，我们直接一个一个循环查找，因此时间复杂度为O(n)。

三.一般方法的优化

一.O(sqrt(n))

我们想，除了1和本身外，至少有1个因子就可以判断他是不是素数了。

而一个合数n可以写成两个因子乘积的形式，而且两个因子也存在大小关系，比如36可以写成1*36或4*9的形式。我们不难推出其中的一个因子一定不超过n 。否则等式就不成立了。

bool isPrime(int number){ for(int i = 2;i*i<=number;i++){ if(number % i == 0){ return false; } } return true; }

n>时，time超过1000ms 

二.筛偶数，找奇数O(sqrt(n))

思路就是除了2以外的所有偶数都是合数，对于奇数嘛，找找有没有可以被奇数因子整除的，比如9，他就可以被3整除

#include<iostream> using namespace std; bool judge_prime(int n){ if(n%2==0&&n!=2)//偶数判断 return false;//false代表不是素数，是合数 else//奇数判断 for(int i=3;i*i<=n;i+=2){ if(n%i==0) return false;//false代表不是素数，是合数 } return true;//默认返回时素数 } int main(){ int n; cin>>n; if(judge_prime(n)){ cout<<"YES"<<endl;//是素数 }else cout<<"NO"<<endl;//不是素数 return 0; } 

 n>时，time 超过1000ms;

三.规律O(sqrt(n)/6)

嗨嗨嗨，先来讲一下素数的出现规律

就是大于等于5的质数一定会和6的倍数相邻。

证明过程如下：

我们可以将大于等于5的质数表示为6x-1，6x，6x + 1，6x + 2，6x + 3，6x + 4，6x + 5，6(x + 1），6(x + 1) + 1 …

以6x为例，6x左侧是6x-1 右侧是6x+1，往后6x+2,6x+3,6x+4都可以写成2(3x+1),3(2x+1),2(3x+2),

这些数都可以被除了1和它自身之外的数整除，所以它们一定不是素数。

再除去6x，本身，剩余的的素数只会出现6x两侧

我们将i++的跨度从刚开始的1变为2，再变到6，有木有变快呢？

#include<iostream> using namespace std; bool judge_prime(int n){ if(n==1) return false;//1不是素数 ，标记为false if(n==2||n==3) return true;//他俩是素数，返回true； if(n%6!=1&&n%6!=5)//根据6的倍数两侧的数是素数进行快速排查 return false; for(int i=5;i*i<=n;i+=6){//更加细致地对性质数进行排查 if(n%i==0||n%(i+2)==0) return false; } return true;//默认返回true； } int main(){ int n; cin>>n; if(judge_prime(n)){ cout<<"YES"<<endl;// }else cout<<"NO"<<endl; return 0; }

n>时，time 超过1000ms;

四.埃氏筛区间找素数

埃拉托斯特尼(百度查的)提出的一种算法，可以算出区间范围内的所有素数。

思路是，质数的倍数一定是合数。换句话说任何一个合数n都可以分解成质数的乘积。且在这个乘积中，必然存在一个质数因子n。

例如 4是合数可以拆成2*2 可以理解2既是质数，又是倍数。

例如 8是合数可以拆成2*4 可以分解成质数的乘积。

我们可以定义一个数组，让所有质数的倍数全都标记一遍。直到所求的区间边界N,这样下来，未被标记的数则为素数。前面一般方法的优化中提到一个合数可以写成两个因数的乘积的形式。

 for(int i = 2;i*i<=number;i++)

所以我们可以利用该思路筛选出N的素数，再通过倍数进行筛选。

例如我们要求1到100内的素数。我们先求出10以内的素数，如 2 3 5 7 再通过倍数进行筛选，为何没有11呢？与36=4*9，36=9*4；类似，我们只需求出较小的质数，再通过倍数就可筛选，例如：22=2*11，可以看成2的11倍。若以11为质数，11*2会与2*11重合。

在图中我用不同颜色的笔来标出质数的倍数。 完成后未被标记的就是素数。这就是埃氏筛的算法。

下面用代码来表达,我们用ture来进行标记，最后如果没有被标记则是素数

#include <iostream> using namespace std; const int N = ; bool sign[N]; void get_primes(int n){ sign[0]=true;//C++中数组中的元素在初始化时，其它未初始化的元素会被默认初始化为对应类型的零值 sign[1]=true;//所以0，1被标记为true；其它位置的值为false未被标记 for(int i=2;i*i<=n;i++){//从2开始标记，标记出2的倍数，再递增到下一个素数 if(!sign[i]){// 没有被标记 for(int j=i+i;j<=n;j+=i){//倍数标记，一直到N的边界 sign[j]=true; /*内层for的另一种写法 for(int j=2;j<=n/i;j++){ sign[i*j]=true; }*/ } } } } int main() { int n; cin>>n; get_primes(n); for(int i = 2; i <= n; i++){//输出没有标记的数字，若判断区间是否存在素数则找到一个未标记的素数，falg=1跳出循环即可 if(!sign[i]){ cout << i << endl; } } system("pause"); return 0; }

五.欧拉筛(线性筛)区间找素数

我们回顾之前的做法

 发现有些合数被不同的质数标记，这就增加了我们计算的次数，所以为了避免做重复工作，我们

想想有没有办法可以使得合数只被1个质数标记？

我们从图表中寻找规律发现 6可以分解质因数为2*3；10可以分解质因数为2*5。

我们的想法是，只能被最小的质数标记。

我们从一般方法的优化中得知一个合数n可以写成两个因子乘积的形式，而且两个因子也存在大小关系

唯一分解定理

同时我们也可以引申出唯一分解定理，意思是任何一个大于1的正整数n都可以分解成若干个素数（质因数）的连乘积，并且如果不考虑排列顺序，这种分解就是唯一的。

以24举例，24可以写成24/2=12;12/2=6;6/2=3;所以24=2*2*2*3；

所以我们只需要找到最小的质因数时就可以了，比如24的2，后续的质因子就停止标记。

那我们就不难推出：对于一个合数，其只被最小质因数筛，而与之相对应的就是非本身的最大因数，比如对于28这个数字，非本身最大因数是14，与之对应的最小质因数则为2，这样就可以做到筛选时不重复且不漏掉合数，总结出公式则为：

非自身最大因数 X 最小质因数 = 该合数

#include <iostream> using namespace std; #define N  int primes[N];//素数数组，用来存放素数 int count;//素数地个数 bool sign[N];//标记素数 void get_primes(int n){ sign[0]=true; sign[1]=true; for(int i=2;i<=n;i++){//从2开始遍历，来逐个进行查找 if(!sign[i]){//如果当前数未被标记，则是素数 primes[count++]=i; }//把素数存入素数数组 //接下来进行倍数查找，并筛选出最小质素的倍数 for(int j=0;primes[j]<=n/i;j++){//素数一直循环到n/i,i是倍数， //因为我们只需经将素数的倍数进行标记，就可以完成全部的筛选，这里体现了i的两个功能一个是充当倍数，一个充来充当筛选的索引 sign[primes[j]*i]=true;//质数的倍数进行标记 if(i%primes[j]==0)//由于primrs数组中的值为递增存储，可以选出数值i的最小质数。 break; } } } int main() { int n; cin >> n; get_primes(n); for (int i = 0; i < count; i++) cout << primes[i] << " "; cout << endl; return 0; }