数学知识-质数

文章目录 一、质数二、质数的判定——试除法1. 实现思路2. 实现代码 三、分解质因数——试除法1. 实现思路2. 实现代码 四、筛质数1. 朴素筛法1.1 实现思路1.2 实现代码 2. 线性筛法2.1 实现思路2.2 实现代码

一、质数 质数又称素数。一个大于 1 1 1 的自然数，除了 1 1 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定 1 既不是质数也不是合数）。质数具有如下性质：（1） 质数 p p p 的约数只有两个： 1 1 1 和 p p p。（2） 初等数学基本定理：任一大于 1 1 1 的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。（3） 质数的个数是无限的。（4） 若 n n n 为正整数，在 n 2 n^{2} n2 到 ( n + 1 ) 2 (n+1)^{2} (n+1)2 之间至少有一个质数。（5） 所有大于 10 10 10 的质数中，个位数只有 1 ， 3 ， 7 ， 9 1，3，7，9 1，3，7，9。 二、质数的判定——试除法

题目描述

给定 n n n 个正整数 a i a_i ai​，判定每个数是否是质数。

输入格式

第一行包含整数 n n n。 接下来 n n n 行，每行包含一个正整数 a i a_i ai​。

输出格式

共 n n n 行，其中第 i i i 行输出第 i i i 个正整数 a i a_i ai​ 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100 1 ≤ a i ≤ 2 31 − 1 1 ≤ a_i ≤ 2^{31−1} 1≤ai​≤231−1

输入样例

2 2 6

输出样例

Yes No

具体实现

1. 实现思路 暴力写法：可以从质数的常规定义出发，首先判断这个数是不是大于等于 2 的，然后判断在 2 到这个数之间是否还有别的约数，如果没有，那么这个数就是质数，反之就不是质数。该暴力写法的时间复杂度是 O ( n ) O(n) O(n)。对上述暴力写法进行优化时，需要利用到质数的一个性质。当 d d d 可以整除 n n n 时，显然， n / d n/d n/d 也可以整除 n n n。例如，当 n = 12 n=12 n=12 时， 3 3 3 是 12 12 12 的约数， 4 4 4 也是 12 12 12 的约数，他们是成对存在的。因此，在我们枚举的过程中，只需要枚举其中较小的一个即可，优化过后的时间复杂度是 O ( n ) O(\sqrt{n}) O(n ​)。 2. 实现代码 #include <bits/stdc++.h> using namespace std; bool is_prime(int x) { //判断这个数是否大于等于 2 if (x < 2) { return false; } //判断是否还有别的约束 for (int i = 2; i <= x / i; i ++ ) { if (x % i == 0) { return false; } } return true; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; if (is_prime(x)) { puts("Yes"); } else { puts("No"); } } return 0; } 三、分解质因数——试除法

题目描述

给定 n n n 个正整数 a i a_i ai​，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n n n。 接下来 n n n 行，每行包含一个正整数 a i a_i ai​。

输出格式

对于每个正整数 a i a_i ai​，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。 每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1 ≤ n ≤ 100 1≤n≤100 1≤n≤100 2 ≤ a i ≤ 2 × 1 0 9 2≤a_i≤2×10^{9} 2≤ai​≤2×109

输入样例

2 6 8

输出样例

2 1 3 1 （空行） 2 3 （空行）

具体实现

1. 实现思路 我们需要注意的是，质因数的底数必须是质数。暴力写法：从小到大枚举 n n n 的所有质因数，如果 n n n 模 i i i 等于 0 0 0，就求出 i i i 的次数即可。 void divide(int x) { for (int i = 2; i <= x; i ++ ) { if (x % i == 0) //i一定是质数 { int s = 0; while (x % i == 0) { x /= i; s ++ ; } cout << i << ' ' << s << endl; } } } 随后在对 n n n 进行是否大于 1 1 1 的判断即可。对上述写法进行优化，我们需要使用质数的如下性质。 x x x 的质因子最多只包含一个大于 x \sqrt{x} x ​ 的质数。如果有两个，这两个因子的乘积就会大于 x x x，矛盾。然后，我们 i i i 从 2 2 2 遍历到 x \sqrt{x} x ​。 用 x / i x / i x/i，如果余数为 0 0 0，则 i i i 是一个质因子。 s s s 表示质因子 i i i 的指数， x / = i x /= i x/=i 为 0 0 0，则 s + = 1 s+=1 s+=1， x = x / i x = x / i x=x/i 。最后检查是否有大于 x \sqrt{x} x ​ 的质因子，如果有，输出。时间复杂度便会从 O ( n ) O(n) O(n) 降低到 O ( n ) O(\sqrt{n}) O(n ​)。 2. 实现代码 #include <bits/stdc++.h> using namespace std; void divide(int x) { for (int i = 2; i <= x / i; i ++ ) { if (x % i == 0) //i一定是质数 { int s = 0; while (x % i == 0) { x /= i; s ++ ; } cout << i << ' ' << s << endl; } } if (x > 1) { cout << x << ' ' << 1 << endl; } cout << endl; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; divide(x); } return 0; } 四、筛质数

题目描述

给定一个正整数 n n n，请你求出 1 ∼ n 1∼n 1∼n 中质数的个数。

输入格式

共一行，包含整数 n n n。

输出格式

共一行，包含一个整数，表示 1 ∼ n 1∼n 1∼n 中质数的个数。

数据范围

1 ≤ n ≤ 1 0 6 1≤n≤10^{6} 1≤n≤106

输入样例

8

输出样例

4

具体实现

1. 朴素筛法 1.1 实现思路 首先，我们将所有的数放入一个数组当中，然后从前往后观察，依次将每一个数的倍数删除掉。经过这样筛选过后，剩下的数就都是质数。 1.2 实现代码 #include <bits/stdc++.h> using namespace std; const int N= 1000010; //cnt表示质数的个数 int primes[N], cnt; bool st[N]; void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) { //跳出本次循环 continue; } //primes[]数组存储质数 primes[cnt ++ ] = i; //去除倍数 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; } 2. 线性筛法 2.1 实现思路 算法核心： n n n 只会被其的最小质因子筛掉。当 n n n 为一个合数的时候，如果 i i i 比 n / p j n / pj n/pj 还小，就一定会被筛掉。判断 i   m o d   p j = = 0 i \bmod pj == 0 imodpj==0， p j pj pj 一定是 i i i 的最小质因子， p j pj pj 也一定是 p j ∗ i pj*i pj∗i 最小质因子。判断 i   m o d   p j ! = 0 i \bmod pj != 0 imodpj!=0, p j pj pj 一定小于 i i i 的所有质因子， p j pj pj 也一定是 p j ∗ i pj*i pj∗i 最小质因子。于一个合数 x x x，假设 p j pj pj 是 x x x 的最小质因子，当 i i i 枚举到 x / p j x / pj x/pj 的时候，一定会被筛掉。 2.2 实现代码 #include <bits/stdc++.h> using namespace std; const int N= 1000010; 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 ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) //primes[j]一定是i的最小质因子 { break; } } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }