プロジェクトオイラーQ3 Pythonの非常に遅い

Question

私は、コードで完全な初心者だ、だから私は、私はプロジェクトオイラーの問題を解くことによって、より良い得ることができると思った、私は13195の素因数は5です」という質問3.

に貼り付けました。 、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]) 

Answer 1

このコードのスピードアップにはいくつかのことがあります。 まず、数学と素数のいくつかの性質についてもう少し知りました。

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))) 

Answer 2

私のために働いた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))