数论——质数与约数

一、质数

质数(素数)

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

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

思想

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

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

代码

1. 判断质数

#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");
		else
			puts("No");
	} 
	return 0;
}

2. 分解质因数

输入格式

第一行包含整数 n。

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

输出格式

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

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

输入样例：

2
6
8

输出样例：

2 1
3 1

2 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.筛法

1. 埃氏筛法$O(nloglogn)$ （调和级数+欧拉常数证明）

// 埃氏筛 
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;
		}
	}
}

2. 欧式筛法（线性筛）$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;
}

为什么不需要写 $j<cnt$

• primes数组中存有小于等于 i 的所有质数
• 当 i 是合数， p[j] 为 i 的最小质因子时 break
• 当 i 是质数， p[j] 为 i 时 break

二、约数

如果一个数a除以另一个数b的余数为0，即 a%b == 0, 则b是a的约数

1.试除法求约数

用 x 除以 1 到 x 的所有数，如果余数是0，则把除数加到答案中

用于约数是成对存在的且对称轴为 $\sqrt{x}$ ，所以只需用 x 除以 1 到 根号 $\sqrt{x}$ 之间的数，如果余数是0，则把除数 $d$ 以及 $x/d$ 加到答案中。

代码如下

输入格式

第一行包含整数 n

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

输出格式

输出共 n 行，其中第 i 行输出第 i 个整数 $a_i$ 的所有约数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> get_divisors(int x) {
	vector<int> rt;
	for (int i = 1; i <= x / i; i ++) {
		if (x % i == 0) {
			rt.push_back(i);
			if (i != x / i)
				rt.push_back(x / i); 
		}			
	}
	sort(rt.begin(), rt.end());
	return rt;
}

int main() {
	int n;
	cin >> n;
	while (n --) {
		int x;
		cin >> x;
		auto res = get_divisors(x);
		for (auto &v: res) {
			cout << v << " \n"[v == res.back()];
		}
	}
	return 0;
}

2.约数个数

$N={\prod }_{i=1}^k{p}_i^{a_i}$

N的约数个数: ${\prod }_{i=1}^k(a_i+1)=(a_1+1)(a_2+1)...(a_k+1)$

以 12 为例

$12=2^2+3^1$

2的约数有 $1，2，3，4，6，12$
约数个数：$（2+1）?（1+1）=6$，

相当于求每个约数的组合个数，前面有三种可能:

2^0 = 1, 2^1 = 2 , 2^2 = 4

后面有两种可能:

3^0 = 1 , 3^1 = 3 。

将前面三种可能和后面两种可能进行排列组合，总共有2 * 3种可能。

代码如下

输入格式

第一行包含整数 n。

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

输出格式

输出一个整数，表示所给正整数的乘积的约数个数

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	unordered_map<int, int> primes; 
	while (n --) {
		int x;
		cin >> x;
		for (int i = 2; i <= x / i; i ++) 
			while (x % i == 0) {
				primes[i] ++;
				x /= i;
			}
		if (x > 1)	primes[x] ++;
	}
	int ans = 1;
	for (auto &p: primes)	ans = (long long)ans * (p.second + 1) % mod;
	cout << ans << endl;
	
	return 0;
}

3.约数之和

$N={\prod }_{i=1}^k{p}_i^{a_i}$

N的约数之和: ${\prod }_{i=1}^k(p_i^0+p_i^1+...+p_i^{a_i})=(p_1^0+p_1^1+...+p_1^{a_1})(p_2^0+p_2^1+...+p_2^{a_2})...(p_k^0+p_k^1+...+p_k^{a_k})$

代码如下

输入格式

第一行包含整数 n。

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

输出格式

输出一个整数，表示所给正整数的乘积的约数之和

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	unordered_map<int, int> primes; 
	while (n --) {
		int x;
		cin >> x;
		for (int i = 2; i <= x / i; i ++) 
			while (x % i == 0) {
				primes[i] ++;
				x /= i;
			}
		if (x > 1)	primes[x] ++;
	}
	LL ans = 1;
	for (auto &prime: primes) {
		int p = prime.first, a = prime.second;
		LL t = 1;
		while (a --) 
			t = (p * t + 1) % mod;
		ans = ans * t % mod;
	}
	cout << ans << endl;
	
	return 0;
}

4.最大公约数——欧几里得算法（辗转相除法）

欧几里得算法原理：

• 对于两个非负整数a和b，设a >= b。
• 如果b等于0，那么a就是最大公约数。
• 否则，将a除以b得到余数r，即a % b，然后递归调用gcd(b, r)。

证明步骤：

1. 基本情况： 当b等于0时，gcd(a, b)返回a。这是因为任何数与0的最大公约数都是其自身，所以算法在这里终止。
2. 递归步骤： 当b不等于0时，gcd(a, b)调用自身，但交换了参数的位置：gcd(b, a % b)。这是为了确保每次递归中，较小的数作为新的b，而余数（a % b）作为新的a。
3. 正确性： 欧几里得算法的正确性基于以下观察：如果d是a和b的一个公约数，那么它也是b和a % b（余数）的公约数。因此，递归调用保持了最大公约数的不变性。
4. 终止： 由于每次递归都将较大的数缩小为较小的数，而递归终止的条件是b等于0，所以算法最终会在gcd(b, a % b)中终止，返回最大公约数。

因此，这段代码通过递归调用，按照欧几里得算法的原理，计算了两个非负整数的最大公约数。

代码如下

C++ 内置求最大公约数函数见下面链接

C++ 内置求最大公约数函数

#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

int main() {
	int n;
	cin >> n;
	while (n --) {
		int a, b;
		cin >> a >> b;
		cout << gcd(a, b) << endl;
	}
	
	return 0;
}