Goldbach's Conjecture - 2つの素数の和として偶数を書く方法の数を調べる

Question

与えられた正の偶数を2つの素数の和として書く方法の数を知りたい。

瞬間に、私はこのコードを持っている：それは作品

n = int(input(">")) 
def genprimes(n):#generate primes from 2 to n 
    primes = [] 
    for i in range(2,n): 
     prime = True 
     for a in range(2,i): 
      if i % a == 0: 
       prime = False 
     if prime == True: 
      primes.append(i) 
    return primes 

pairs = [] 
primes = genprimes(n) 

for prime1 in primes: 
    for prime2 in primes: 
     if prime1 + prime2 == n and [prime1,prime2] not in pairs and [prime2,prime1] not in pairs: 
      pairs.append([prime1,prime2]) 
print(len(pairs)) 

が、nは10,000っぽい以上になるとき、それは少し遅くなります。誰もがこの値を見つけるより効率的な方法を考えることができるので、高い値に対して迅速な結果が得られますか？

Answer 1

2つの低速アルゴリズムがあります。

素数のリストを取得するには、各素数を個別にチェックしてください。素数のリストを得る最も速い方法は、あらかじめ作成された素数のリストを使用することです - それが私がそのような問題のために行うことです。 2 ** 16（65,536）までの素数のリストは6542個の整数しか取らず、そのリストをモジュールに格納します。このようなリストを最初から得るための最も速い方法として一般に認められているSieve of Eratosthenesを使用することをお勧めします。

次に、各ペアの素数を対象番号に追加するかどうかを試してみます。各素数について、pの方がはるかに速く、n-pも素数であるかどうかを確認してください。 @Shubhamが示唆しているように、n-pをバイナリ検索でチェックすることはできますが、2つのインデックスを持つ方が速いでしょう。のチェックのために、pともう1つ下がっています。プライムリストをセットにコピーして、n-pがリストにあるかどうかをチェックするのが最も簡単です。これらの最後の2つのテクニックは、nの順ですが、最大10,000までの数字の場合、オーバーヘッドがどのテクニックが最善であるかに影響する可能性があります。そして、はい、そのような問題のために10,000はあまり大きくありません。最後に、メモリが問題でない場合、@BoulderKeithは、ブール値リスト（True/False）のリストとしてプライムリストを残し、n-pが素数であるかどうかを素早くチェックすることができると指摘しています。これは、 、すべての技術。

Answer 2

これは、プログラムの両方の部分を最適化することによって効率的に行うことができます。

まず、O(nlog(log(n))にn点で最大の素数を生成することができるエラトステネスのふるいを使用して素数を生成することによってgenprimes()を最適化することができます。その後

、我々は素数のリストを持っていたら、私たちは次の操作を行うことができます：プライムリストを

• 反復と素数を選択し、p1を言います。
• バイナリ検索を使用すると、n-p1もプライムリストに存在するかどうかを確認します。

p = number of primes till n場合、この部分の複雑さはO(plog(p))になります。

@PaulHankinは、@SrujanKumarGullaの回答から、素数リストを取得したらO(p)ソリューションを構築できます。第二の部分の

実装（最初の部分は、標準Sieve of Eratosthenesある）：

# prime list is assumed to be sorted. It will be if it's generated 
# using Sieve of Eratosthenes 

def solutions(n, prime_list): 
    low = 0, high = len(prime_list)-1 
    sol = [] 
    while low < high: 
     temp = prime_list[low] + prime_list[high] 
     if temp == n: 
      sol.append((prime_list[low], prime_list[high],)) 
     elif temp < n: 
      low += 1 
     else: 
      high -= 1 

    return len(sol) 

Answer 3

これは効率的に素数を生成するエラトステネスのふるいを使用し、次いで場合見Roryの提案から実際のソリューションでありますn-primeも素数です。

これが真である解決策の数は、重複を避けるために半分にする必要があります。メモリが問題ではない場合、あなたはで、さらに速度を最適化することができます

n = int(input(">")) 
def genprimes(n): 
    limitn = n+1 
    not_prime = set() 
    primes = [] 

    for i in range(2, limitn): 
     if i in not_prime: 
      continue 
     for f in range(i*2, limitn, i): 
      not_prime.add(f) 
     primes.append(i) 
    return primes 

nos=0 
primes = genprimes(n) 

for prime in primes: 
    if n-prime in primes: 
     nos += 1 
print(str(int((nos/2)+0.5))) 

Answer 4

：

1）の配列を持つ2..nから配列を構築する私が素数である場合は、[i]が真=。

2）< = i < n/2 array [i]とarray [n-i]の両方が真であるかどうかを確認してください。そうであれば、iとn-iはペアになります。 （iの上限をn/2に設定すると、重複を削除する必要もありません。）

アルゴリズム全体がO（n log n）です。

これはPythonではなくC＃で行いましたが、10秒でn = 100,000,000のすべてのペアを見つけることができました。私は別のものを追加したくない

Answer 5

def prim(n): 
     primes = [] 
     for num in range(1, n + 1):  # current number check 
      limit = int(num ** 0.5) + 1 # search limit 
      for div in range(2, limit): # searching for divider 
       if (num % div) == 0: # divider found 
        break    # exit the inner loop 
      else:      # out of the inner loop 
       primes.append(num)  # no divider found hence prime 
     return(primes) 

    num = int(input('Input an even number: ')) 
    primes = prim(num)     # create list of primes 

    for i in range(num//2 + 1): 
     if num % 2 != 0: 
      print(num, 'not even'); break 
     if i in primes and (num - i) in primes: 
      print(i, '+', num - i) 
""" 
Examples: 
========= 
Input an even number: 18 
1 + 17 
5 + 13 
7 + 11 

Input an even number: 88 
5 + 83 
17 + 71 
29 + 59 
41 + 47 

Input an even number: 17 
17 not even 
"""