〔Fancy Zone〕质数与约数
题单介绍
# 
**一、质数**
质数（Prime Number），又称素数，指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。
例如，2、3、5、7、11 等都是质数。
**质数的性质：**
1. 质数只有两个正因数（1 和它本身）。
2. 所有大于 10 的质数中，个位数只有 1、3、7、9。
**判断一个数是否为质数的方法：**
1. 试除法：从 2 到该数的平方根依次尝试能否整除该数，如果都不能整除，则该数为质数。
- 例如，判断 13 是否为质数，因为 √13 ≈ 3.6，所以只需尝试 2、3 是否能整除 13，均不能整除，所以 13 是质数。
**质数的筛选（埃氏筛法）：**
可以通过筛选的方法找出一定范围内的所有质数。
基本思路：从 2 开始，将每个质数的倍数都标记为合数，剩下未被标记的就是质数。
```python
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
if is_prime[p]:
for i in range(p * p, n + 1, p):
is_prime[i] = False
p += 1
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
```
**二、约数**
约数，又称因数，指能够整除一个整数的数。
例如，6 的约数有 1、2、3、6。
**求一个数的约数的方法：**
1. 分解质因数法：将该数分解为质因数的乘积，然后通过组合质因数的方式得到所有约数。
- 例如，12 = 2² × 3，所以 12 的约数有 1、2、3、4、6、12。
2. 试除法：从 1 到该数的平方根依次尝试能否整除该数，能整除的数和其对应的商都是该数的约数。
**最大公约数（Greatest Common Divisor，GCD）**
指两个或多个整数共有约数中最大的一个。
常见求最大公约数的方法：
1. 欧几里得算法（辗转相除法）：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是 0 为止。此时的除数就是最大公约数。
```python
def gcd(a, b):
while b!= 0:
a, b = b, a % b
return a
```
**最小公倍数（Least Common Multiple，LCM）**
指两个或多个整数公有的倍数中最小的一个。
求最小公倍数的方法：两个数的乘积等于这两个数的最大公约数与最小公倍数的积。
即：LCM(a, b) = a × b / GCD(a, b)
例如，求 12 和 18 的最小公倍数，先求其最大公约数为 6，所以最小公倍数为 12 × 18 / 6 = 36。
在信息学竞赛中，质数与约数的相关知识经常用于解决一些数论问题，如整数分解、因数个数计算、最大公约数和最小公倍数的求解等。熟练掌握这些知识对于提高解题能力和效率至关重要。
---
###### *题单贡献者：*
###### *题目编排：[djxstc](https://www.luogu.com.cn/user/1020627)*
###### *笔记补充：[BunDragon126](https://www.luogu.com.cn/user/927203)*
###### 质数与约数笔记 © Fancy Zone OI 版权所有 | 感谢上方贡献人员！