算法基础课|数学知识|质数

发表于 分类于 浏览： 阅读时长 ≈ 2 分钟
ACWing 算法基础课笔记 质数相关

质数

质数的定义：大于1的自然数，只包含1和本身连个约束

质数的判定——试除法

从2到n-1，遍历判断元素能否整除n，如果可以整除则说明不是质数

1
2
3
4
5
6
7
8
9
10
11
12
def solve(n):
    if n < 2: return False
    for i in range(2, n):
        if n % i == 0: return False
    return True

# 优化
def solve(n):
    if n < 2: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0: return False            
    return True

优化：

  • 性质一：如果d能够整除n，则 n / d 也能整除n

    比如：4能够整除12，则3也能够整除12， n的约数一定是成双成对的，因此可以枚举每一对中较小的数

Untitled

分解质因数

时间复杂度：O(sqrt(n))

优化：

  • 性质一：n中最多只包含一个大于根号n的质因子

    因为如果有两个，乘起来就大于n了

1
2
3
4
5
6
7
8
9
10
11
12
def solve(n):
	# 质因子，一定是从2开始的
	# 不用担心合数，如果能被4整除也一定可以被2整除 
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n = n // i
            print(i, cnt)
		# 如果n有一个大于根号n的质因子，则单独处理
    if n > 1: print(n, 1)

筛质数

时间复杂度：O(nlogn) 更具体一点 调和级数 O(nlnn)左右

1
2
3
4
5
6
7
8
9
10
11
12
def solve(n):
    st = [False] * (n + 1)
    cnt = 0
    for i in range(2, n + 1):
        j = i + i
				# 如果没有被筛过，就是质数
        if not st[i]: cnt += 1
				# 遍历这个数所有的倍数 它的倍数都不是 质数
        while j <= n:
            st[j] = True
            j += i
    return cnt

优化：

不需要遍历所有数的倍数，只需要遍历质数的倍数

  • 性质一：1 - N 中有 $N/ln N$ 个质数

时间复杂度：O(nloglogn) 约等于O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 埃氏筛法
# O(nloglogn) 约等于O(n)
def solve(n):
    st = [False] * (n + 1)
    cnt = 0
    for i in range(2, n + 1):
        j = i + i
				# 如果这个数是质数
        if not st[i]: 
            cnt += 1
            while j <= n:
                st[j] = True
                j += i
    return cnt

优化：

n只会被它的最小质因子筛掉，欧拉筛，线性筛