【算法】数论基础——唯一分解定理（算术基本定理）python

定义

唯一分解定理：也叫做算数基本定理:
任意一个大于1的整数N，都可以唯一分解为若干个质数的乘积

换句话说，任何大于1的整数n可以表示为：

例如：
30 = 2^1 * 3^1 * 5^1
100 = 2^2 * 5^2

进入正题

那么怎么去实现呢？很简单

示例实现

def prime_factor(n):
    factor = []
    for i in range(2, n + 1):
        while n % i == 0:
            n //= i
            factor.append(i)
        if n == 1:
            break
    return factor


print(prime_factor(100))
# [2, 2, 5, 5]

热身训练

分解质因数 https://www.lanqiao.cn/problems/1559/learning/?page=1&first_category_id=1&problem_id=1559

仅仅需要注意一下输出的格式即可

题解code：

def prime_factor(n):
    factor = []
    for i in range(2, n + 1):
        while n % i == 0:
            n //= i
            factor.append(i)
        if n == 1:
            break
    return factor


a, b = map(int, input().split())
for i in range(a, b + 1):
    print(i, end='=')
    print(*prime_factor(i), sep='*')

实战演练

k的倍数 https://www.lanqiao.cn/problems/4278/learning/?page=1&first_category_id=1&tag_relation=intersection&problem_id=4278

题解code：

def prime_factor(n):
    factor = []
    for i in range(2, n + 1):
        while n % i == 0:
            n //= i
            factor.append(i)
        if n == 1:
            break
    return factor


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = []
    for i in a:
        ans += prime_factor(i)
    res = 1
    for i in range(len(ans)):
        res *= ans[i]
        if res % k == 0:
            print('Yes')
            break
    else:
        print('No')

扩展衍生

如果一个数 n 是完全平方数，则其每个质因子的次数必定为偶数。

给出证明：

判断一个数是否为完全平方数

基于上述性质，判断一个数是否为完全平方数：
1.对该数进行质因数分解。
2.检查每个质因数的指数是否都是偶数。
3.如果所有质因数的指数都是偶数，则该数是完全平方数；否则，不是完全平方数。

示例实现code：

from collections import defaultdict

# 唯一分解定理
def prime_factors(n):
    factors = []
    for i in range(2, n + 1):
        while n % i == 0:
            factors.append(i)
            n //= i
        if n == 1:
            break
    return factors

# 如果有质因数的指数为奇数，则返回0
def is_square(n):
    cnt = defaultdict(int)
    factors = prime_factors(n)
    for i in factors:
        cnt[i] += 1
    for i in cnt.values():
        if i % 2 == 1:
            return 0
    return 1


n = int(input())
print(is_square(n))

举一反三

第十二届蓝桥杯省赛C++ A/B组真题 完全平方数 https://www.acwing.com/problem/content/description/3494/

题目描述：

一个整数 $a$ 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 $b$，使得 $a=b^2$。

给定一个正整数 $n$，请找到最小的正整数 $x$，使得它们的乘积是一个完全平方数。

输入格式

输入一行包含一个正整数 $n$。

输出格式

输出找到的最小的正整数 $x$。

数据范围

对于 $30$ 的评测用例，$1\le n\le 1000$，答案不超过 $1000$。
对于 $60$ 的评测用例，$1\le n\le 10^8$，答案不超过 $10^8$。
对于所有评测用例，$1\le n\le 10^{12}$，答案不超过 $10^{12}$。

输入样例1：

12

输出样例1：

3

输入样例2：

15

输出样例2：

15

思路分析：

完全平方数其质因子次数一定为偶数，
如果其质因子次数为奇数，我们就将ans * 此质因子

实现:

from collections import defaultdict


def prime_factors(n):
    factors = []
    for i in range(2, n + 1):
        while n % i == 0:
            factors.append(i)
            n //= i
        if n == 1:
            break
    return factors


n = int(input())
res = prime_factors(n)
ans = 1
cnt = defaultdict(int)
for i in res:
    cnt[i] += 1
for key, value in cnt.items():
    if value % 2 == 1:
        ans *= key
        if ans == n:
            break
print(ans)

结果超时（因为此题n为1e12）
现在需要想想怎么优化

发现当前的代码在质因数分解部分的时间复杂度较高
从2到n逐个检查是否为质因数，这导致时间复杂度O(n)。
对于 n≤1e12 来说效率较低。
需要改进，优化质因数分解的时间复杂度：
预处理得到质数表，只需要检查质数作为可能的因子，而不是所有整数。

题解code：

from collections import defaultdict


def Euler(n):  # 通过欧拉筛得到质数表
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break
    return primes


def prime_factors(n):
    factors = []
    for prime in prime_list:
    	# 在质因数分解时只遍历到sqrt(n)
        if prime * prime > n:   
            break
        while n % prime == 0:
            factors.append(prime)
            n //= prime
    # 如果剩下的n是一个大于sqrt(n)的质数，也应加入factors中
    if n > 1:  
        factors.append(n)
    return factors


prime_list = Euler(int(1e7))
n = int(input())
res = prime_factors(n)
ans = 1
cnt = defaultdict(int)
for i in res:
    cnt[i] += 1
for key, value in cnt.items():
    if value % 2 == 1:
        ans *= key
        if ans == n:
            break
print(ans)

不会预处理质数表的小伙伴可以点此进入详细讲解

素数筛法：埃氏筛与欧拉筛

总结

通过理解和应用唯一分解定理，我们可以更好地分析和解决与整数相关的复杂问题。

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢