Pythonは本当に大きな整数の問題を表示しますか？

Question

600851475143の最高素因数を計算するコードがあります。

def PRIME(a):    #Check if no is prime 
    f = 0 
    i = 2 
    while(i < a/2):   #No factor of a no can be greater than a/2 
     if (a % i == 0): 
      f = 1 
      break 
     i = i + 1 

    if(f == 1): 
     return 0 
    else: 
     return 1 


def PFIND(a): 
    for i in range(1, 100000): #Iteratively check if the no is prime 
     if PRIME(a/2 - i):  #No factor of a no can be greater than a/2. 
      if (a % (a/2 - i) == 0): 
       return (a/2 - i) 
print PFIND(600851475143) 

しかし、コードは何度も実行され、何も出力されません。

Answer 1

Pythonの大きな整数のサポートは問題ありません。私はあなたの問題は、あなたが非常に遅いアルゴリズムをやっていて、要因を突き止める力とあなたの要素がプライムであるかどうかをテストすることです。これらの2つのテストの順序を逆転させるだけであれば（つまり、それが重要かどうかをテストし、それがプライムかどうかをテストする）、それはずっと高速になります。

おそらく問題は、より洗練されたアルゴリズムを使用することでした。たぶん、ブルートフォースの代わりにRabin-Miller testを使うべきでしょう。

Answer 2

テスト用に膨大な数で始めるのではなく、アルゴリズムを小さな数字で試してみてください。その後、徐々に大きな数字を試してみてください。関数の所要時間をプロットする - timeitモジュールを使用することをお勧めします。次に、関数があなたが試している数にどれくらいの時間がかかるかを推測して推定します。

あなたのアルゴリズムは、それが終わっていないように見えるほど長い時間がかかります。

while(i < a/2): 

の

Answer 3

あなたのループ条件は、あなたのアルゴリズムテイクO（N）時間を作っています。

簡単な変更で、これがO（√ N）に改善されます。

hi = int(math.sqrt(a) + 1)  # +1 in case of rounding error. 
while i <= hi: 

Answer 4

私は、Pythonが大きな整数で素晴らしい仕事をしていることを発見しました。すでに述べたように、あなたはこのナットをひっくり返すために2回のブルートフォーステストを使用しています。

はこれを試してみてください：

a = 600851475143 
q = 2 

while q <= a/2: 
    if not a % q: 
     a /= q 
     p = q 
    else: 
     q += 1 

print p 

Answer 5

私は私があなたの目的のために働くようになってきた、過去に素数としなければならないいくつかの趣味のコードを書きました。コードは次のとおりです。

def isPrime(n, primes=[]): 
    """ Return True iff n is a prime number. 
      If primes is non-empty, return true iff n is co-prime to every number in primes. """ 

    if not len(primes): 
      if n <= 2: 
        return True 
      elif n%2 == 0: 
        return False 
      else: 
        prime = True 
        for i in range(3, n, 2): 
          if n%i == 0: 
            prime = False 
        if prime: 
          return True 
    else: 
      for p in primes: 
        if not n%p: 
          return False 
      return True 

def next(n, primes): 
    """ Return a number p such that 
      1. p is co-prime to every number in primes 
      2. p>n and p-n is as small as possible""" 

    curr = n+1 
    while 1: 
      if isPrime(curr, primes): 
        return curr 
      else: 
        curr += 1 

def generate(n): 
    """ Yield the first n prime numbers""" 

    primes = [2] 
    curr = 2 
    for _ in range(n-1): 
      p = next(curr, primes) 
      primes.append(p) 
      curr = p 
      yield p 

def primeNumbers(n): 
    """ return a list of prime numbers such that all numbers in the list are at most n 
      1 is a prime number""" 

    answer = [] 
    if n <= 2: 
      answer.append(n) 
    else: 
      for i in range(3, n+1, 2): 
        prime = True 
        for p in answer: 
          if i%p == 0: 
            prime = False 
            break 
        if prime: 
          answer.append(i) 

    return answer 

def PFIND(n): 
    primes = primeNumbers(n) 
    primes.reverse() 
    for p in primes: 
     if n%p == 0: 
      return p 

これはすべきです。

ホープこれは

Answer 6

Pythonの長い数のサポートは非​​常に冗長、よくテストされているのに役立ちますので、私はそれが問題だ疑い。私があなたのコードについて気づいたのは、ループの各反復で、最適化されておらず、値a/2を数回計算するということです。しかし、もしあなたがそれを修正したとしても、おそらくは遅い可能性があります。finding prime factorsは特に大きな数字のために非常に時間がかかることがあります。

私は、最良の方法はより良いアルゴリズムを見つけることだと思います。ここでは、数値のすべての素因数を計算する、私が見つけたコードから派生したコードがあります。私はそれをPythonに変換し、見つけた最大の要因を追跡するために単純化しました。それは素早く{71、839、1471、& 6857}のテストケースの正解を返しました。

def maxprimefactor(n): 
    """ find the largest prime factor of a positive integer """ 
    maxfactor = None 
    divisor = 2 
    while divisor*divisor <= n: 
     if n % divisor: 
      divisor += 1 
     else: 
      maxfactor = divisor 
      n /= divisor 
    if n != 1: 
     maxfactor = n 

    return maxfactor if maxfactor else 1 

print maxprimefactor(600851475143) 
# 6857