数论——质数与约数

news/2024/7/5 1:44:45

一、质数

质数(素数)

一个大于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;
}
  1. 分解质因数
输入格式

第一行包含整数 n。

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

输出格式

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

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

输入样例：
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 ( n l o g l o g n ) O(nloglogn) 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;
		}
	}
}
  1. 欧式筛法（线性筛） O ( n ) O(n) 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 < c n t j<cnt 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，则把除数加到答案中

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

代码如下

输入格式

第一行包含整数 n

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

输出格式

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

#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 = ∏ i = 1 k p i a i N=\prod_{i=1}^{k}p_i^{a_i} N=∏i=1k​piai​​

N的约数个数: ∏ i = 1 k ( a i + 1 ) = ( a 1 + 1 ) ( a 2 + 1 ) . . . ( a k + 1 ) \prod_{i=1}^{k}(a_i+1) = (a_1+1)(a_2+1)...(a_k+1) ∏i=1k​(ai​+1)=(a1​+1)(a2​+1)...(ak​+1)

以 12 为例

12 = 2 2 + 3 1 12=2^2+3^1 12=22+31

2的约数有 1 ， 2 ， 3 ， 4 ， 6 ， 12 1， 2， 3， 4， 6， 12 1，2，3，4，6，12
约数个数： （ 2 + 1 ） ⋅ （ 1 + 1 ） = 6 （2 + 1） \cdot （1 + 1） = 6 （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 a_i ai​。

输出格式

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

#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 = ∏ i = 1 k p i a i N=\prod_{i=1}^{k}p_i^{a_i} N=∏i=1k​piai​​

N的约数之和: ∏ 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 ) \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}) ∏i=1k​(pi0​+pi1​+...+piai​​)=(p10​+p11​+...+p1a1​​)(p20​+p21​+...+p2a2​​)...(pk0​+pk1​+...+pkak​​)

代码如下

输入格式

第一行包含整数 n。

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

输出格式

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

#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;
}

http://lihuaxi.xjx100.cn/news/1886462.html

相关文章

计算机网络：应用层（一）

计算机网络：应用层（一）

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…
阅读更多...
Mac如何设置control+space切换上一中输入法

Mac如何设置control+space切换上一中输入法

#设置方法# *搜索输入法 系统设置-搜索&#xff1a;输入法&#xff0c;并点击键盘快捷键 *点击输入法&#xff0c;勾选&#xff1a;选择上一个输入法&#xff0c;点击完成。
阅读更多...
算法----K 和数对的最大数目

算法----K 和数对的最大数目

题目 给你一个整数数组 nums 和一个整数 k 。 每一步操作中&#xff0c;你需要从数组中选出和为 k 的两个整数&#xff0c;并将它们移出数组。 返回你可以对数组执行的最大操作数。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3,4], k 5 输出&#xff1a;2 解释&…
阅读更多...
uniapp使用u-empty以及其相关属性

uniapp使用u-empty以及其相关属性

Uni-app 是一款基于 Vue.js 的跨平台开发框架&#xff0c;可以用于同时开发多个平台的应用程序。其中&#xff0c;u-empty 是 Uni-app 提供的一个组件&#xff0c;用于展示空状态的页面。 u-empty 组件有以下几个相关属性&#xff1a; image&#xff1a;设置空状态显示的图片。…
阅读更多...
漏洞复现-泛微云桥 e-Bridge SQL注入（附漏洞检测脚本）

漏洞复现-泛微云桥 e-Bridge SQL注入（附漏洞检测脚本）

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…
阅读更多...
Log4j.xml配置说明

Log4j.xml配置说明

介绍 Log4j 2 是一款广泛使用的 Java 日志框架&#xff0c;它支持多种日志级别、异步日志、过滤器等功能&#xff0c;并且具有高性能和可扩展性。以下是 Log4j 2 的详细配置说明&#xff1a; 配置文件名称和存放位置&#xff1a;Log4j 2 的配置文件名可以是任意有效的文件名&a…
阅读更多...
python在线读取传奇列表，并解析为需要的JSON格式

python在线读取传奇列表，并解析为需要的JSON格式

python在线读取传奇列表，并解析为需要的JSON格式，以下为传奇中使用的TXT列表格式， [Server] ; 使用“/”字符分开颜色，也可以不使用颜色，支持以前的旧格式，只有标题和服务器标题支持颜色 ; 标题/颜色代码(0-255)|服务器标题/颜色代码(0-255)|服务器名称|服务器IP|服务器端…
阅读更多...
算法通关村第十七关 | 黄金挑战 | 跳跃游戏

算法通关村第十七关 | 黄金挑战 | 跳跃游戏

1.跳跃游戏 原题&#xff1a;力扣55. 逐步判断下一步的覆盖范围&#xff0c;根据范围去推断是否能到达终点&#xff0c;不用计较每一步走到哪里。 public boolean canJump(int[] nums) {// 题目规定 nums 长度大于等于1if (nums.length 1) {return true;}int cover 0;// f…
阅读更多...
最新文章

Copyright @ 2022~2023