二次的素数

Question

プロジェクトオイラーの問題27（https://projecteuler.net/problem=27）について質問しています。私は動作しないか、または十分に速く動作しないコードを書いています。プログラミングに慣れておらず、エラーの意味を完全に理解していません。

とにかく、どの整数が$ a、b $と$ | a |、| b | < 1000 $は$ n^2 + an + b $に続き、$ n = 0 $で始まる連続する素数の最大集合を生成します。まず、$ n = 0 $項を素数にしてチェーンを始めるためには、$ b $自体が素数でなければならないことに気づく。私は、可能なすべての素数をbにループし、各整数$ -1000 < < 1000 $をチェックし、生成された連続する素数の連鎖の長さを測定するコードを書いた。私はそれを以下に含めました：

n=int(input("Set a bound for range of a and b: ")) 


def is_prime(n): 
if n==1: 
    return False 
elif n==2 or n==3: 
    return True 
elif (n % 2 == 0) or (n % 3 == 0): 
    return False 
elif all(n % i != 0 for i in range(2, ceil(n**0.5+1))): 
    return True 
else: 
    return False 

def seive(n): 
primes=[] 
for i in range(n): 
    if is_prime(i)==True: 
     primes.append(i) 
for j in primes: #j can't be allowed to be negative since when m=0 (the first term), we must have m**2+k*m+j prime. Therefore j must be chosen from primes 
    for k in range(-n,n,1): 
     chain=[] 
     for m in range(0,n): 
      while is_prime(m**2+k*m+j) == True and m**2+k*m+j>0: 
       chain.append(m**2 + k*m + j) 
       details = [j,k,len(chain)] 
return details 

print(seive(n)) 

誰かが私が間違っていたことを説明し、それを働かせるヒントを教えてください。ありがとう！

Answer 1

この問題を分析すると、2つの制約が生じます。 bは素数でなければならず、aは1-bより大きくなければならない。しかし、aとbの可能な範囲は非常に小さく、このような制約を見つけ出し、ソリューションに組み込む価値はありません。ミスをしたり、足で自分を撃ったりするための追加の機会を作ります。

考慮すべき唯一の制約は、nがbの倍数である場合、n^2 + a*n + bはnで割り切れる必要があります。したがって、素数の連鎖は、遅くともn = bで停止しなければならず、これは素数性のチェックが必要な可能性のある最大数の上限を与える。つまり、素数検査の可能性が最も高い候補は、2,000,000未満でなければなりません。これは、素数検定として試行除算の代わりに集合メンバシップを使用する場合に有用な制限を与える。

コメントでヒントされているように、タスクは最後にテストされた係数のセットと結果のチェーンの長さを見つけることではありません。あなたは素数の最長連鎖を与える係数aとbを見つけて、そのペアの積を出力するよう求められます。したがって、チェーンテストとその結果を処理する方法を変更する必要があります。あなたは少しそれをクリーンアップし、重複を削除する場合

はおそらく、あなたがより良いあなたのコードを理解するだろう（例えばis_prime(x)はx >= 2、ひいてはx > 0を意味し、それだけで素数判定のためのテストの後に積極性のためのテストを入れても意味がありません） 。個々のビットとピースが単一の責任を持ち、シバン全体に統合される前に別々にテスト/チューニングできるように、コードをリファクタリングすることも役立つはずです。

コードを作業形態にしたら、Code Reviewに投稿したいと思うかもしれません。これは、あなたが探しているようなフィードバックのためのより適切な場所です。

P .:エンベロープをプッシュしようとすると、私が最初に述べたような制約が実際には非常に面白くなりますが、問題を解決するには可能な限り簡単な解決方法が必要です。 Pythonでさえ数秒もかからないはずです。