质数也叫素数，指大于1的自然数中，除了1和它本身外不再有其他因数的自然数，比如2、3、5、7、11、13。
以下是有关质数的一些板子:

素数筛

常用的质数筛算法有试除法、线性筛和埃氏筛。我个人喜欢用的是埃氏筛。时间复杂度：试除法>埃氏筛>线性筛

试除法

MX = 10 ** 5 + 1
primes = []
[primes.append(i) for i in range(2, MX) if all(i % p != 0 for p in primes if p * p <= i)]
# 等同于
# for i in range(2, MX):
#     if all(i % p != 0 for p in primes if p * p <= i):
#         primes.append(i)

埃氏筛

MX = 10 ** 5 + 1
is_prime = [True] * MX
primes = set()
is_prime[1] = False
for i in range(2, MX):
    if is_prime[i]:
        primes.add(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False
# primes = sorted(primes)

线性筛

MX = 10 ** 5 + 1
is_prime = [True] * MX
primes = []

for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
    for p in primes:
        if i * p >= MX:
            break
        is_prime[i * p] = False
        if i % p == 0:
            break

质因数分解

s = set()
i = 2
while i * i  <= x:
    if x % i == 0:
        s.add(i)
        x //= i
        while x % i == 0:
            x //= i
    i += 1
# 注意:如果除不尽, 剩余数x又不是1, 那么x也是质因数
if x > 1:
    s.add(x)