输入一个数字并找出它的因素——错误答案

Question

我为写了一个简单的代码来输入一个数字，找到它的因子并打印出来：

import math
n=int(input("Enter your number : "))
i=int(math.sqrt(n)+1)
while i !=0:
if n%i==0:
print(i)
i=i-1

但由于某种原因，它并没有给我正确的答案。

输出：

Enter your number : 35
5
1

Answer 1

好吧，我很愚蠢，正在为自己的问题写答案。。。。

import math
n= 35#int(input("Enter your number : "))
i=int(math.sqrt(n)+1)
while i !=0:
if n%i==0:
print(i)
print(n/i)
i=i-1

这实际上是最有效的方法

Answer 2

这将快速获得因子列表，首先获得素数列表和每个因子的幂，然后在所有组合中将它们相乘。请注意，候选数不一定都是素数，但它们确实包括所有素数。

import itertools
def gen_candidates():
yield 2
yield 3
c = 0
while True:
c += 6
yield c - 1
yield c + 1
def gen_prime_factors_with_powers(x):
for c in gen_candidates():
if c * c > x:
yield (x, 1)
return
power = 0
while x % c == 0:
power += 1
x //= c
if power:
yield (c, power)
if x == 1:
break
def product(lst):
prod = 1
for item in lst:
prod *= item
return prod

def get_factors(x):
factors = [[(pf ** i) for i in range(1 + power)]
for pf, power in gen_prime_factors_with_powers(x)]
return sorted([product(lst) for lst in itertools.product(*factors)])
print(get_factors(12345678909876543210))

显然，如果主要因素本身很大，那么它仍然可能需要一些时间，但它只会搜索到较大的：

• 第二大素数
• 最大素因子的平方根

它不会搜索到x，只有在素数的最坏情况下，它才会搜索到x的平方根。