质数
基本概念
如果一个正整数只能被1和自身整除，那么这个正整数就是质数(也称素数),否则称该正整数为合数
质数的判定——试除法
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> using namespace std; int n; bool is_prime(int n) { //0 和 1既不是质数，也不是合数 if(n < 2) return false; for(int i = 2;i <= n / i ;i++) if(n % i == 0) return false; return true; } int main() { //输入 scanf("%d",&n); while(n--) { //调用函数 + 输出 int t; scanf("%d",&t); if(is_prime(t)) puts("Yes"); else puts("No"); } }
算法模板
试除法判定质数 bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true; }
疑难点剖析
一、算法实现思路
扫描2~N \sqrt{N} N之间的所有整数，依次检查它们能否整除N，若都不能整除，那么N是质数，否则N是合数。所以时间复杂度是O(N \sqrt{N}
N)
二、算法实现的优化
这个算法从暴力的角度走，是可以直接从2枚举到N-1的，只要这里面都没有能够整除N的，那么就可以确定这个N是质数，但是这种做效率挺慢的，时间复杂度是O(N)
比如现在N是17，先去整除4进行尝试，假如再尝试8, 12，16其实都没有意义了，因此就根据性质进行优化。
乘法运算中，乘数 x 另一个乘数 = 积。 当 n 能够整除 d 的时候，结果是 n/d,同时，它也就是另一个乘数，那么n也肯定是能够整除n/d的。 因为我们是从2开始枚举，d依次被赋值为2,3，，，所以d < = n/d。依据这个实现对枚举区间的缩小
分解质因数
算术基本定理： 对于任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：
N = P1c1 P2c2 …Pmcm
其中ci都是正整数，Pi都是质数，且满足P1 < P2 < … < Pm
例题描述
参考代码(C++版本)
#include <iostream> #include <algorithm> using namespace std; void divide(int n) { //试除法枚举所有的数 for(int i = 2;i <= n / i;i++) if(n % i == 0) { int s = 0; while(n % i == 0) { n /= i; s++; } printf("%d %d\n",i,s); //要清楚i才是底数 } if(n > 1) printf("%d %d\n",n,1); puts(""); } int main() { //输入 int n; scanf("%d",&n); while(n--) { //调函数 int x; scanf("%d",&x); divide(x); } return 0; }
算法模板
一、算法实现流程图：
二、算法的代码实现：
试除法分解质因数 void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
疑难点剖析
一、明白题目需求
题目要的是将传入的数据分解为底数是/质数，指数是整数，分解结果的乘积等于原数据，输出的时候，要从小到大排列。
例如：
6就是21 x 31，因此就输出 2 1和3 1
48就是24 x 31，因此就输出2 4 和 3 1
二、指数的获取
8 = 23 = 2 x 2 x 2;
那么在代码层面，我们可以采用逆向思维，倒着对8进行运算，统计它进行的除法次数，也就是相乘的次数了。同时，也就是指数了。
质数筛选
例题描述
参考代码(C++版本)
// 埃氏筛选法 #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int primes[N],cnt; bool st[N]; void get_primes(int n) { for(int i = 2;i <= n;i++) { if(!st[i]) { primes[cnt++] = n; //利用现有数，将这些数的倍数去掉 for(int j = i+i; j <= n;j += i) st[j] = true; } } } int main() { //输入 int n; cin >>n; //调用函数 get_primes(n); //输出 cout << cnt <<endl; return 0; } //线性筛选法 算法原理：n只会被最小质因子筛掉 #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int primes[N],cnt; bool st[N]; void get_primes(int n) { for(int i = 2;i <= n;i++) { //如果是质数，就把加到数组中去 if(!st[i]) primes[cnt ++] = i; //从小到大枚举所有的质数 for(int j = 0; primes[j] <= n/i;j++) { //把prims[j] * i筛掉 st[primes[j] * i] = true; if(i % primes[j] == 0) break; //primes[j]一定是i的最小质因子 } /* 1、i % pj == 0 pj一定是i的最小质因子，pj一定是pj*i的最小质因子 2、i % pj != 0 pj一定小于i的所有质因子，pj也一定是pj * i的最小质因子 */ } } int main() { //输入 int n; cin >>n; //调用函数 get_primes(n); //输出 cout << cnt <<endl; return 0; }
算法模板
一、埃氏筛法——用当前已有的质数去消去它们的倍数
首先，将2到n范围的所有整数获取到。其中，最小的数字2是质数，将2的所有倍数划去。表中剩余的数字中，最小的是3，它不能被更小的整除，所有它是质数，再将所有3的倍数划去。以此类推如果表中剩余的最小数字是m时，m就是质数。然后将表中所有m的倍数都划去。像这种反复操作，就能够依次枚举n以内的质数。
举个栗子：
1.1、 算法实现流程如下：
1.2、算法代码实现：
埃氏筛法求素数 int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) continue; primes[cnt ++ ] = i; for (int j = i; j <= n; j += i) st[j] = true; } }
1.3、算法的时间复杂度 = O(NloglogN)
二、线性筛法
线性筛选的核心是—— 传入的整数n只会被最小质因子筛掉
2.1、算法实现流程：
2.2、算法代码实现：
线性筛法求素数 int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } }
2.3、算法时间复杂度 = O(N)
疑难点剖析
清楚primes数组和st数组是分别用来维护素数集合和被筛除数据的集合
