兩部分問題：1）試圖確定600851475143的最大素數，我在網上找到了該程序，該程序似乎有效。問題是，盡管我了解程序的基本功能，但我很難弄清楚它的工作原理。另外，我想請您介紹一下可能知道的尋找主要因素的任何方法（也許無需測試每個數字）以及您的方法如何工作。這是我在網上找到的用于質因子分解的代碼：n = 600851475143i = 2while i * i < n: while n % i == 0: n = n / i i = i + 1print (n)#takes about ~0.01secs2）為什么該代碼比僅用于測試速度并且沒有其他實際目的的代碼要快得多？i = 1while i < 100: i += 1#takes about ~3secs
3 回答
慕虎7371278
TA貢獻1802條經驗 獲得超4個贊
這個問題是我在Google搜尋時彈出的第一個鏈接"python prime factorization"。如@ quangpn88所指出的，該算法對于諸如的完美平方是錯誤的（?。?。n = 4, 9, 16, ...但是，@ quangpn88的修復也不起作用，因為如果最大素數出現3次或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
慕運維8079593
TA貢獻1876條經驗 獲得超5個贊
好像人們在做Euler項目一樣，您自己編寫解決方案。對于想要完成工作的其他所有人，有primefac模塊可以非?？焖俚赝瓿纱罅抗ぷ鳎?/p>
#!python
import primefac
import sys
n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))
- 3 回答
- 0 關注
- 556 瀏覽
添加回答
舉報
0/150
提交
取消