項目歐拉Q3的Python很慢

我在編碼一個完整的初學者，所以我想我可以通過解決項目歐拉問題的更好，我被困在問題3項目歐拉Q3的Python很慢

「的13195的首要因素是5 ，7,13和29. 數字600851475143的最大素數是多少？「

我的代碼適用於較小的數字示例，但是當我嘗試運行較長的代碼時，如何使代碼更高效？

n=3 #factors 
l=[] 
flag = True 
while(n<600851475143): 
    a=3 
    if (600851475143%n==0): 
    while(a<n): 
     if n%a!=0: 
     a+=2 
     else: 
     flag = False 
     break 
    if(flag): 
     l.append(n) 

    n+=2 
print(l[len(l)-1])

來源

2017-05-09 Angelrina

如果像你說的，你是新來再編碼有提高你的技能不是解決上項目歐拉的問題，因爲許多這些挑戰的更好的方法涉及見解數學，優化或其他領域，至少在我看來。更好的是，您應該儘可能地尋找純粹的編程教程或練習。無論如何，祝你好運！ –

查看大O特別是普通函數順序部分https://en.wikipedia.org/wiki/Big_O_notation – quantik

是的，你有兩個'while'循環嵌套。它隨輸入值的平方增長。看看你是否可以將你的想法扁平化爲一個while循環。 –

有幾件事你可以做，以加快此代碼。首先是更熟悉數學和素數的一些性質。

Prime numbers

Integer factorization

Why do we check up to the square root of a prime number to determine if it is prime or not

的另一件事是（至少對我來說），你的代碼是真的很難讀...嘗試讓你的意圖更加清晰。

我試圖想出一個在Python中的解決方案，它在我的電腦上運行0.15s。

#!/usr/bin/env python 
import math 

def square_root_as_int(x): 
    return int(math.sqrt(x)) 

def is_prime(number): 
    if number == 1: 
    return False 
    for x in range(2, square_root_as_int(number) + 1): 
    if x == number: 
     next 
    if number % x == 0: 
     return False 
    return True 

def factors_of_(number): 
    factors = [] 
    for x in range(2, square_root_as_int(number) + 1): 
    if number % x == 0: 
     factors.append(x) 
     factors.append(number/x) 
    return factors 

factors = factors_of_(600851475143) 
primes = [] 
for factor in factors: 
    if is_prime(factor): 
    primes.append(factor) 
print max(primes) 

# Bonus: "functional way" 
print max(filter(lambda x: is_prime(x), factors_of_(600851475143)))

來源

2017-09-16 21:39:06

您也可以使用generators，這對我很有幫助。

下面是一個例子：

# Set variables 
number = 600851475143 
primeFactorList = [] 

def primeList(number): 
    # Make list of prime numbers < 'number' 
    for x in range(2, number+1): 
     isPrime = True 
     # Don't calculate for more than the sqrt of number for efficiency 
     for y in range(2, int(x**0.5)+1): 
      if x % y == 0: 
       isPrime = False 
       break 
     if isPrime: 
      yield x 

# Calculate primes using primeList and check for prime factors of 'number' 
for i in primeList(number): 
    if i > number**0.5: 
     break 
    if number % i == 0: 
     primeFactorList.append(i) 

# Print largest prime factor of 'number' 
print(max(primeFactorList))

來源

2018-01-11 16:59:42 Mawxder

項目歐拉Q3的Python很慢

回答

相關問題