两部分问题：
这是我在网上找到的用于素数分解的代码 [注意：此代码不正确。请参阅下面 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
这个问题是我google时弹出的第一个链接"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
好的。所以你说你了解基础知识，但你不确定它是如何工作的。首先，这是对它源于的 Project Euler 问题的一个很好的回答。我对这个问题做了很多研究，这是迄今为止最简单的回应。
为了解释的目的，我会让n = 20. 要运行真正的 Project Euler 问题，让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。
外循环声明 whilei * i不大于n（因为最大的素因数永远不会大于 的平方根），在内循环运行后n添加1到。i
内部循环声明 while均i分为n，替换n为n除以i。这个循环不断地运行，直到它不再是真的。对于n=20and i=2，n被 替换10，然后又被 替换5。因为2没有均匀地分成5，所以循环停止，n=5外循环结束，产生i+1=3。
最后，因为3squared 大于5，外部循环不再是true并打印 的结果n。
感谢您发布此信息。在意识到它是如何工作的之前，我一直在查看代码。希望这是您在回复中寻找的内容。如果没有，请告诉我，我可以进一步解释。
看起来人们正在做 Project Euler 的事情，你自己编写解决方案。对于其他想要完成工作的人来说，有一个primefac 模块可以非常快速地处理非常大的数字：
#!python
import primefac
import sys
n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))
对于素数生成，我总是使用埃拉托色尼筛法：
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
"""
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])
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
27的最大质因数不是3吗？上面的代码可能是最快的，但它在 27 上失败了，对吧？27 = 3*3*3 以上代码返回 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]
如果您正在寻找维护良好的预先编写的代码，请使用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 进行了测试。
另一种方法：
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]
代码错误为 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)
我的代码：
# 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)
TESTING，（注意，我在每个循环中添加了一个 COUNT 来测试优化）
# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')
我认为可以轻松修改此代码以获得（最大因素）或其他任何需要。我对任何问题持开放态度，我的目标是针对更大的素数和因数进一步改进这一点。
如果您想使用 numpy，这里有一种方法可以创建一个包含不大于 n 的所有素数的数组：
[ i for i in np.arange(2,n+1) if 0 not in np.array([i] * (i-2) ) % np.arange(2,i)]
看看这个，它可能对你的理解有所帮助。
#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 = ' ')
这是我的 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))
第一个问题的答案在几分之一秒内就出现了。
以下是有效生成给定数的素数的两种方法：
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')
由于没有人试图用旧的好reduce方法来破解它，我将接受这个职业。此方法对于此类问题不灵活，因为它对参数数组执行重复操作的循环，并且默认情况下无法中断此循环。在我们实现了自己的interupted reducefor 中断循环之后，大门打开了，如下所示：
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]
为了提高效率，您可能希望使用位于特定范围内的预生成素数，而不是该范围内的所有值。
你不应该循环到数字的平方根！有时可能是对的，但并非总是如此！
10 的最大素数是 5，大于 sqrt(10)（3.16，aprox）。
33 的最大素数是 11，大于 sqrt(33)（5.5,74，aprox）。
您将这与规定的适当性混淆了，即如果一个数字的素因数大于其 sqrt，则它必须至少有另一个其他素因数小于其 sqrt。所以，如果你想测试一个数字是否是素数，你只需要测试到它的 sqrt。
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()
处理 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
n=int(input("Enter the number"))
if n==1 : #because the below logic doesn't work on 1
print(n)
for i in range(2 , n+1):
if n%i==0 :
n1=i #get factor
for b in range(2,n+1): #check if it is prime
if ((n1%b)==0) & (n1==b):
print(n1)
elif (n1%b)==0 or n1<b: #if not then pass
break
我确信这是最糟糕的逻辑，但它是我在 .py 中所拥有的所有知识，该程序将从用户那里获取一个数字并打印它的所有因子数字，例如 12 它将给出 2,3