素数生成プログラムによるメモ生成

Question

n-1番目の素数で始まり、n番目の素数を生成してインクリメントするPythonクラスを持っています。次にリスト内のすべての素数で階数（sqrt（候補））まで割ります。 しかし、私のクラスはちょうどどこかの無限ループに入ってしまい、なぜ私は理解できません。

class prime_list(): 
    def __init__(self): 
     self.primelst = [1] 
     self.n = 1 

    def increment(self): 
     self.n+=1 
     candidate = self.primelst[-1]+1 
     limit = int(math.floor(math.sqrt(candidate))) 
     prime = True 
     while True: 
      for p in self.primelst: 
       if p>limit: 
        break 
       if (candidate % p) == 0: 
        prime = False 
        break 
      if prime: 
       self.primelst.append(candidate) 
       return 
      else: 
       candidate += 1 
       limit = int(math.floor(math.sqrt(candidate))) 
       prime = True 

if __name__=="__main__": 
    p = prime_list(): 
    p.increment() 

Answer 1

問題は、プライムリストに開始値として1を入れることです。 increment関数は、1で割り切れない数値を検索します。そのような数字はないので、永遠に検索します。

最初の最小の素数として2で始めるか、最初の素数の生成を処理する特殊なケースを追加する必要があります。

Answer 2

これはまさに言語またはアルゴリズムに関する質問ではなく、デバッグの質問です。 ループ内に4つのprintステートメントを追加すると（条件分岐ごとに1つずつ）、プログラムが終了しないように見える理由をすぐに知ることができます。 調査を通して自分自身で何が起きているのかを理解することはずっと良いことです（誰かに魚を与える代わりに魚を教える...）。

幸運を祈る！

Answer 3

のは、実行してみましょう：

// self.primelst = [1] 
// self.n = 1 

def increment(self): 
     self.n+=1 // self.n = 2 
     candidate = self.primelst[-1]+1 //candidate = 2 
     limit = int(math.floor(math.sqrt(candidate))) // limit = 1 
     prime = True // prime = True 
     while True: 
      for p in self.primelst: // p = 1 
       if p>limit: // False 
        break // Does not go here 
       if (candidate % p) == 0: // 2 % 1 == 0: True 
        prime = False // prime = False 
        break // breaks 
      if prime: // False 
       self.primelst.append(candidate) // Does not go here 
       return // Does not return 
      else: // Goes here 
       candidate += 1 // candidate = 3 
       limit = int(math.floor(math.sqrt(candidate))) // limit = 1 
       prime = True // prime = True 

ので、whileループは無限に繰り返します。アルゴリズムは間違っています。

Answer 4

他者によって記述の修正に加えて、いくつかの注意事項、：

• あなたはself.nを使用していないと、Pythonのリストは、その長さを知っているので、それを必要としません。
• しかし、複雑な計算を避けるために、の数を覚えてをチェックすることができます。
• primelstは識別子として醜いです：そのようなランダムな母音を除外することは非常に非 - Pythonであり、識別子名（ "リスト"）にタイプ名を含めることはダックタイピングの精神に反します。コンテナに複数の名前を付けるだけです。
• 短い機能が好ましい。 add-to-listロジックからのプライム検出を考慮に入れると、コードが大幅に簡略化されます。ネストされたループの中にブレークとリターンの両方を持つことは、従うのが難しいです。
• メイン 'インクリメント'関数をジェネレータにして、生成中にオンデマンドで素数にアクセスすることができます。 :)
• 標準ライブラリには、（a）無制限のカウントされたループを作成し、（b）範囲内のすべての除数を単純化するツールがあります。

したがって：

class prime_list(): 
    def __init__(self): 
     self.primes = [2] 
     self.to_use = 1 


    def test(self, candidate): 
     # Check if we need to expand the list of used primes. 
     # Written a bit paranoid-ly 
     while len(self.primes) > self.to_use: 
      next = self.primes[self.to_use] 
      # Note the mathematical rearrangement. :) 
      if candidate <= next * next: self.to_use += 1 
     # Test all the primes <= sqrt(candidate). 
     return all(candidate % p != 0 for p in self.primes[:self.to_use]) 


    def __iter__(self): 
     import itertools 
     for candidate in itertools.count(3): 
      if self.test(candidate): 
       self.primes.append(candidate) 
       yield candidate 


if __name__ == "__main__": 
    my_primes = prime_list() 
    for p in my_primes: 
     print "Generated:", p 
     if p > 1000000: break 
    print "Number of primes generated:", len(my_primes.primes) 

Answer 5

カールKnechtelの答えは正しいが、低迷しています。問題はto_useがあまりにも早く進んでいることです。

私の修正バージョンです - 私はコメントを削除しました。

class prime_list(): 
    def __init__(self): 
     self.primes = [2] 
     self.to_use = 0 


def test(self, candidate): 
    next = self.primes[self.to_use] 
    if candidate >= next * next: 
     self.to_use += 1 
     print candidate, next 
    return all(candidate % p != 0 for p in self.primes[:self.to_use]) 


def __iter__(self): 
    import itertools 
    for candidate in itertools.count(3,2): 
     if self.test(candidate): 
      self.primes.append(candidate) 
      yield candidate 


if __name__ == "__main__": 
    my_primes = prime_list() 
# print my_primes.primes[0] 
    for p in my_primes: 
     print "Generated:", p 
     if p > 1000000: break 
     sum += p 
    print "Number of primes generated:", len(my_primes.primes)