目录
- 定义
- 进入正题
- 热身训练
- 实战演练
- 扩展衍生
- 判断一个数是否为完全平方数
- 举一反三
- 总结
定义
唯一分解定理：也叫做算数基本定理:
任意一个大于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 a a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b b b，使得 a = b 2 a = b^2 a=b2。
给定一个正整数 n n n，请找到最小的正整数 x x x，使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n n n。
输出格式
输出找到的最小的正整数 x x x。
数据范围
对于
30
30\\%
30 的评测用例，
1
≤
n
≤
1000
1 ≤ n ≤ 1000
1≤n≤1000，答案不超过
1000
1000
1000。
对于
60
60\\%
60 的评测用例，
1
≤
n
≤
1
0
8
1 ≤ n ≤ 10^8
1≤n≤108，答案不超过
1
0
8
10^8
108。
对于所有评测用例，
1
≤
n
≤
1
0
12
1 ≤ n ≤ 10^{12}
1≤n≤1012，答案不超过
1
0
12
10^{12}
1012。
输入样例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)
不会预处理质数表的小伙伴可以点此进入详细讲解
素数筛法：埃氏筛与欧拉筛
总结
通过理解和应用唯一分解定理，我们可以更好地分析和解决与整数相关的复杂问题。
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
