【算法】数论基础——唯一分解定理（算术基本定理）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')

总结

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

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