当前位置：首页 > news >正文

数论——质数

news 来源：原创 2024/5/9 8:09:08

数论——质数

质数(素数)

一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数，这个数就是质数。

1.试除法(O(sqrt(n)))

思想

一个数 x 分解成两个数的乘积，则这两个数中，一定有一个数大于根号 x，一个数小于根号x。

所以，可以用 x 除以 2 ~ 根号x 中的每个数，如果出现了余数为 0,则这个数不是质数，如果没有出现余数为 0,则这个数是质数。

代码

判断质数

#include <cmath>
#include <cstdio>using namespace std;bool is_prime(int x) {if (x < 2)	return false;for (int i = 2; i <= sqrt(x); i ++) if (x % i == 0)return false;return true;
}int main() {int n;scanf("%d", &n);while (n --) {int x;scanf("%d", &x);if (is_prime(x))puts("Yes");elseputs("No");} return 0;
}

分解质因数

输入格式

第一行包含整数 n。

接下来 n行，每行包含一个正整数 $a_i$ 。

输出格式

对于每个正整数 $a_i$ ，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

输入样例：
2
6
8
输出样例：
2 1
3 12 3

#include <iostream>using namespace std;void divide(int x) {for (int i = 2; i <= x / i; i ++) if (x % i == 0) {int s = 0;while (x % i == 0) {++ s;x /= i;}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;
}

2.筛法

埃氏筛法 $O (n l o g l o g n)$ （调和级数+欧拉常数证明）

// 埃氏筛 
void get_primes(int n) {for (int i = 2; i <= n; i ++) {if (!st[i]) {primes[cnt ++] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}}
}

欧式筛法（线性筛） $O (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)	break;}}
}

证明

2-n的每一个合数都会被其最小质因子筛掉
- i % p[j] == 0:p[j] 一定是 i 的最小质因子，所以 p[j] 一定是 p[j]*i 的最小质因子。
- i % p[j] ！= 0: p[j] 一定小于 i 的最小质因子，所以 p[j] 一定是 p[j]*i 的最小质因子。

代码

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

#include <iostream>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 ++) {st[primes[j] * i] = true;if (i % primes[j] == 0)	break;}}
} int main() {int n;cin >> n; get_primes(n);cout << cnt << endl;return 0;
}