按照 geeks for geeks 网站上给出的寻找质因数的解决方案,我不太明白为什么他们在第 16 行使用 n 的平方根(for i in range(3,int(math.sqrt(n)) )+1,2): )
https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
# Python program to print prime factors
import math
# A function to print all prime factors of
# a given number n
def primeFactors(n):
# Print the number of two's that divide n
while n % 2 == 0:
print 2,
n = n / 2
# n must be odd at this point
# so a skip of 2 ( i = i + 2) can be used
for i in range(3,int(math.sqrt(n))+1,2):
# while i divides n , print i ad divide n
while n % i== 0:
print i,
n = n / i
# Condition if n is a prime
# number greater than 2
if n > 2:
print n
如果有人能理解下面给出的反例,这就是我无法遵循的逻辑。
Every composite number has at least one prime factor less than or equal to square root of itself. This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than √n, then a.b > √n, * √n, which contradicts the expression “a * b = n”.
最佳答案
这是简单的算术。如果r
是n
的平方根,则r * r == n
。如果将 r
乘以大于它的值,结果将大于 n
。因此不可能有任何其他质因数大于 r
。
因此,继续循环超过平方根是没有意义的,因为它永远找不到任何东西。
关于python - 质因数,帮助理解平方根的用途,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62544216/