Python 查找质因数
- 2025-01-03 08:40:00
- admin 原创
- 96
问题描述：
两部分问题：
为了确定 600851475143 的最大素因数，我在网上找到了一个似乎可行的程序。问题是，我很难弄清楚它到底是如何工作的，尽管我了解程序的基本工作原理。另外，我希望你能解释一下你所知道的任何寻找素因数的方法，也许不需要测试每个数字，以及你的方法是如何工作的。
这是我在网上找到的质因数分解代码[注意：此代码不正确。请参阅下面 Stefan 的回答以获取更好的代码。]：
n = 600851475143
i = 2
while i * i < n:
while n % i == 0:
n = n / i
i = i + 1
print(n)
#takes about ~0.01secs
为什么那段代码比这段代码快那么多，这只是为了测试速度，除此之外没有其他实际用途？
i = 1
while i < 100:
i += 1
#takes about ~3secs
解决方案 1：
这个问题是我在谷歌上搜索时弹出的第一个链接"python prime factorization"。正如@quangpn88 指出的那样，对于完全平方数，这种算法是错误的（！），例如n = 4, 9, 16, ...然而，@quangpn88 的修复也不起作用，因为如果最大素因数出现 3 次或更多次，它将产生不正确的结果，例如n = 2*2*2 = 8或n = 2*3*3*3 = 54。
我认为 Python 中正确的强力算法是：
def largest_prime_factor(n):
i = 2
while i * i <= n:
if n % i:
i += 1
else:
n //= i
return n
不要在性能代码中使用它，但是对于具有中等大数字的快速测试来说是可以的：
In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop
如果寻求完整的质因数分解，则这是强力算法：
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
解决方案 2：
好的。所以你说你了解基础知识，但你不确定它的具体工作原理。首先，这是对欧拉计划问题的一个很好的回答。我对这个问题做了很多研究，这是迄今为止最简单的回答。
为了便于解释，我设n = 20。要运行真正的欧拉计划问题，设n = 600851475143。
n = 20
i = 2
while i * i < n:
while n%i == 0:
n = n / i
i = i + 1
print (n)
这个解释使用了两个while循环。关于循环，最重要的一点while就是要记住，它们会一直运行，直到不再运行为止true。
外层循环指出虽然i * i不大于n（因为最大素因数永远不会大于的平方根n），但在内层循环运行后添加1到。i
内循环表示，当i能整除时，用除以 来n代替。此循环持续运行，直到不再成立。对于和，用 代替，然后再用 代替。由于不能整除，循环以 结束，外循环结束，产生。n`nin=20i=2n10525n=5i+1=3`
最后，因为3平方大于5，所以外层循环不再true，并打印出的结果n。
感谢您发布此信息。我看了好久的代码才明白它到底是如何工作的。希望这就是您在回复中寻找的内容。如果不是，请告诉我，我可以进一步解释。
解决方案 3：
看起来人们正在做欧拉计划，你可以自己编写解决方案。对于其他想要完成工作的人，有一个primefac 模块，它可以非常快速地处理非常大的数字：
#!python
import primefac
import sys
n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '
'.join(map(str, factors))
解决方案 4：
对于素数的生成，我总是使用埃拉托斯特尼筛选法：
def primes(n):
if n<=2:
return []
sieve=[True]*(n+1)
for x in range(3,int(n**0.5)+1,2):
for y in range(3,(n//x)+1,2):
sieve[(x*y)]=False
return [2]+[i for i in range(3,n,2) if sieve[i]]
In [42]: %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop
In [43]: %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop
您可以使用Miller-Rabin 素数测试来检查数字是否为素数。您可以在此处找到其 Python 实现。
总是使用timeit模块来计时你的代码，第二个只需要15us：
def func():
n = 600851475143
i = 2
while i * i < n:
while n % i == 0:
n = n / i
i = i + 1
In [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop
def func():
i=1
while i<100:i+=1
....:
In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop
解决方案 5：
如果您正在寻找维护良好的预先编写的代码，请使用SymPy中的函数sympy.ntheory.primefactors。
它返回的素因数的排序列表n。
>>> from sympy.ntheory import primefactors
>>> primefactors(6008)
[2, 751]
将列表传递给以max()获取最大的质因数：max(primefactors(6008))
如果您想要素因数n以及它们每个的重数，请使用sympy.ntheory.factorint。
给定一个正整数
n，factorint(n)返回一个包含的素因数n作为键及其各自的多重性作为值的字典。
>>> from sympy.ntheory import factorint
>>> factorint(6008) # 6008 = (2**3) * (751**1)
{2: 3, 751: 1}
该代码针对 Python 3.6.9 和 SymPy 1.1.1 进行了测试。
解决方案 6：
"""
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
"""
from sympy import primefactors
print(primefactors(600851475143)[-1])
解决方案 7：
def find_prime_facs(n):
list_of_factors=[]
i=2
while n>1:
if n%i==0:
list_of_factors.append(i)
n=n/i
i=i-1
i+=1
return list_of_factors
解决方案 8：
27 的最大素因数不是 3 吗？上面的代码可能是最快的，但它在 27 上失败了，对吧？27 = 333 上面的代码返回 1 据我所知.....1 既不是素数也不是合数
我认为这是更好的代码
def prime_factors(n):
factors=[]
d=2
while(d*d<=n):
while(n>1):
while n%d==0:
factors.append(d)
n=n/d
d+=1
return factors[-1]
解决方案 9：
另一种方法：
import sys
n = int(sys.argv[1])
result = []
for i in xrange(2,n):
while n % i == 0:
#print i,"|",n
n = n/i
result.append(i)
if n == 1:
break
if n > 1: result.append(n)
print result
示例输出：
python test.py 68
[2, 2, 17]
解决方案 10：
代码中 100 是错误的。它应该检查 case i * i = n：
我认为应该是：
while i * i <= n:
if i * i = n:
n = i
break
while n%i == 0:
n = n / i
i = i + 1
print (n)
解决方案 11：
我的代码：
# METHOD: PRIME FACTORS
def prime_factors(n):
'''PRIME FACTORS: generates a list of prime factors for the number given
RETURNS: number(being factored), list(prime factors), count(how many loops to find factors, for optimization)
'''
num = n #number at the end
count = 0 #optimization (to count iterations)
index = 0 #index (to test)
t = [2, 3, 5, 7] #list (to test)
f = [] #prime factors list
while t[index] ** 2 <= n:
count += 1 #increment (how many loops to find factors)
if len(t) == (index + 1):
t.append(t[-2] + 6) #extend test list (as much as needed) [2, 3, 5, 7, 11, 13...]
if n % t[index]: #if 0 does else (otherwise increments, or try next t[index])
index += 1 #increment index
else:
n = n // t[index] #drop max number we are testing... (this should drastically shorten the loops)
f.append(t[index]) #append factor to list
if n > 1:
f.append(n) #add last factor...
return num, f, f'count optimization: {count}'
我将其与获得最多投票的代码进行了比较，结果发现速度非常快
def prime_factors2(n):
i = 2
factors = []
count = 0 #added to test optimization
while i * i <= n:
count += 1 #added to test optimization
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors, f'count: {count}' #print with (count added)
测试，（注意，我在每个循环中添加了一个 COUNT 来测试优化）
# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')
我认为可以轻松修改此代码以获取（最大因子）或其他所需的内容。我欢迎任何问题，我的目标是进一步改进此代码，以获得更大的素数和因子。
解决方案 12：
如果你想使用 numpy，这里有一种方法可以创建一个包含不大于 n 的所有素数的数组：
[ i for i in np.arange(2,n+1) if 0 not in np.array([i] * (i-2) ) % np.arange(2,i)]
解决方案 13：
看看这个，它可能会对您的理解有所帮助。
#program to find the prime factors of a given number
import sympy as smp
try:
number = int(input('Enter a number : '))
except(ValueError) :
print('Please enter an integer !')
num = number
prime_factors = []
if smp.isprime(number) :
prime_factors.append(number)
else :
for i in range(2, int(number/2) + 1) :
"""while figuring out prime factors of a given number, n
keep in mind that a number can itself be prime or if not,
then all its prime factors will be less than or equal to its int(n/2 + 1)"""
if smp.isprime(i) and number % i == 0 :
while(number % i == 0) :
prime_factors.append(i)
number = number / i
print('prime factors of ' + str(num) + ' - ')
for i in prime_factors :
print(i, end = ' ')
解决方案 14：
这是我的 Python 代码：它可以快速检查素数，并从最高到最低检查素数因子。如果没有新数字出现，则必须停止。（对此有什么想法吗？）
import math
def is_prime_v3(n):
""" Return 'true' if n is a prime number, 'False' otherwise """
if n == 1:
return False
if n > 2 and n % 2 == 0:
return False
max_divisor = math.floor(math.sqrt(n))
for d in range(3, 1 + max_divisor, 2):
if n % d == 0:
return False
return True
number = <Number>
for i in range(1,math.floor(number/2)):
if is_prime_v3(i):
if number % i == 0:
print("Found: {} with factor {}".format(number / i, i))
最初问题的答案在一瞬间便已出现。
解决方案 15：
以下是两种有效生成给定数字的素因数的方法：
from math import sqrt
def prime_factors(num):
'''
This function collectes all prime factors of given number and prints them.
'''
prime_factors_list = []
while num % 2 == 0:
prime_factors_list.append(2)
num /= 2
for i in range(3, int(sqrt(num))+1, 2):
if num % i == 0:
prime_factors_list.append(i)
num /= i
if num > 2:
prime_factors_list.append(int(num))
print(sorted(prime_factors_list))
val = int(input('Enter number:'))
prime_factors(val)
def prime_factors_generator(num):
'''
This function creates a generator for prime factors of given number and generates the factors until user asks for them.
It handles StopIteration if generator exhausted.
'''
while num % 2 == 0:
yield 2
num /= 2
for i in range(3, int(sqrt(num))+1, 2):
if num % i == 0:
yield i
num /= i
if num > 2:
yield int(num)
val = int(input('Enter number:'))
prime_gen = prime_factors_generator(val)
while True:
try:
print(next(prime_gen))
except StopIteration:
print('Generator exhausted...')
break
else:
flag = input('Do you want next prime factor ? "y" or "n":')
if flag == 'y':
continue
elif flag == 'n':
break
else:
print('Please try again and enter a correct choice i.e. either y or n')
解决方案 16：
因为没有人尝试用旧的好reduce方法破解这个问题，所以我要从事这项工作。这种方法对于此类问题不够灵活，因为它对参数数组执行重复操作的循环，并且默认情况下没有办法中断此循环。在我们实现自己的中断循环后，大门就打开了，interupted reduce如下所示：
from functools import reduce
def inner_func(func, cond, x, y):
res = func(x, y)
if not cond(res):
raise StopIteration(x, y)
return res
def ireducewhile(func, cond, iterable):
# generates intermediary results of args while reducing
iterable = iter(iterable)
x = next(iterable)
yield x
for y in iterable:
try:
x = inner_func(func, cond, x, y)
except StopIteration:
break
yield x
之后，我们可以使用一些与标准 Python Reduce 方法func的输入相同的内容。让我们以以下方式定义它：func
def division(c):
num, start = c
for i in range(start, int(num**0.5)+1):
if num % i == 0:
return (num//i, i)
return None
假设我们要分解一个数字 600851475143，重复使用该函数后，其预期输出应如下：
(600851475143, 2) -> (8462696833 -> 71), (10086647 -> 839), (6857, 1471) -> None
元组的第一项是该方法采用的数字division，并尝试从第二项开始除以最小的除数，最后以该数字的平方根结束。如果不存在除数，则返回 None。现在我们需要从如下定义的迭代器开始：
def gener(prime):
# returns and infinite generator (600851475143, 2), 0, 0, 0...
yield (prime, 2)
while True:
yield 0
最后循环的结果为：
result = list(ireducewhile(lambda x,y: div(x), lambda x: x is not None, iterable=gen(600851475143)))
#result: [(600851475143, 2), (8462696833, 71), (10086647, 839), (6857, 1471)]
并且可以通过以下方式捕获输出素数除数：
if len(result) == 1: output = result[0][0]
else: output = list(map(lambda x: x[1], result[1:]))+[result[-1][0]]
#output: [2, 71, 839, 1471]
笔记：
为了使其更有效率，您可能希望使用位于特定范围内的预生成素数，而不是该范围内的所有值。
解决方案 17：
from functools import lru_cache
primes = []
@lru_cache(maxsize=None)
def factors(n: int):
if n < 2:
return
factors(int(n ** 0.5))
for prime in primes:
if n % prime == 0:
return sorted((prime, *factors(n // prime)))
primes.append(n)
return [n]
if __name__ == '__main__':
print(factors(680000))
print(factors(600851475143))
输出
[2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 17]
[600851475143]
解决方案 18：
优雅地使用集合：
def find_primes(n):
"""Return all prime numbers (inspired by Sieve of Eratosthenes)."""
primes = set(np.arange(2, n))
for i in range(2, n):
primes = primes.difference(np.arange(2 * i, n, i))
return sorted(primes)
解决方案 19：
好的，我利用了所有 > 13 的素数都以 30 加或减 [1,7,11,13] 的形式出现的事实，它非常快：
import sys
x = int(sys.argv[1])
facts = []
for j in [2,3,5,7,11,13]: # low primes first
while x%j ==0 and x > 2:
x//=j
facts += [j]
for p in range(30,int(x**.5)+1,30):
if x == 1: break
for i in [1,7,11,13]:
k,j = p-i,p+i
while x%k==0:
x//=k
facts += [k]
while x%j==0:
x//=j
facts+=[j]
if x>1: facts+=[x]
print(*facts,sep=', ')
输出：
$ time python3 prime_factors.py 600851475143
71, 839, 1471, 6857
real 0m0.014s
user 0m0.011s
sys 0m0.003s
解决方案 20：
你不应该循环到数字的平方根！有时它可能是正确的，但并非总是如此！
10 的最大质因数是 5，它大于 sqrt(10)（约为 3.16）。
33 的最大质因数是 11，它大于 sqrt(33)（约 5.5,74）。
您将其与以下规则混淆了：如果某个数字有一个大于其平方根的素因数，则该数字必须至少有一个小于其平方根的素因数。因此，如果您想测试某个数字是否为素数，则只需测试到其平方根即可。
解决方案 21：
def prime(n):
for i in range(2,n):
if n%i==0:
return False
return True
def primefactors():
m=int(input('enter the number:'))
for i in range(2,m):
if (prime(i)):
if m%i==0:
print(i)
return print('end of it')
primefactors()
解决方案 22：
跳过 2 之后的偶数的另一种方法是：
def prime_factors(n):
factors = []
d = 2
step = 1
while d*d <= n:
while n>1:
while n%d == 0:
factors.append(d)
n = n/d
d += step
step = 2
return factors
