印刷Pythonの

Question

で100以下のすべての双子の素数のペア

は100、私はそれを短くして高速化するために私のコードを最適化するにはどうすればよい

n = 100 # upper limit number 
k = range(3, int((n+1)**0.5) + 1, 2) 


def is_prime_pair(i, i2): 
if i <= 2 or i2 <= 2: 
    return False 
max_div = (i2 ** 0.5) + 1 
for x in k: 
    if (x > max_div or x == i or x == i2): 
     break 
    if (i % x == 0) or (i2 % x == 0): 
     return False 
return True 
for i in range(1, n+1, 2): 
    if is_prime_pair(i, i+2): 
     print "(" + str(i) + ", " + str(i+2) + ")" # Print pairs if prime pair 

の下にありますどのように多くの双子の素数のペアを決定するためのプログラムを書きますか？

Answer 1

まず、素数のリストを作成し、次に双子を検索します。 この方法で、素数であることを2度確認することはありません。

primes = [2] 
for candidate in xrange(3, 100, 2): 
    # Secondly don't try dividing potential primes by every odd number 
    # Just try dividing by the primes you already know! 
    for prime in primes: 
     if prime ** 2 > candidate: 
      primes.append(candidate) 
      break 
     if candidate % prime == 0: 
      break 

# Iterate through all positions in the list except the last to avoid an IndexError 
for i in xrange(len(primes) - 1): 
    if primes[i + 1] - primes[i] == 2: 
     print (primes[i], primes[i + 1]) 

タプルは、すでに希望するようにフォーマットされています。

Answer 2

あなたはほとんどあなたの現在のコードに固執するが、詳細を向上させたい場合は：

1. 使用for i in range(3, ...あなたはプライムペアが1または2で始めることはできませんことを知っているので、次に、あなたがその意志のでif i <= 2...を削除することができます決して起きない。
2. is_prime_pair関数は2つの数値の素数を同時にテストすることを難しくします。むしろ、is_prime関数を使用して単一の数値をテストし、is_prime(i) and is_prime(i+2)を呼び出します。
3. xがmax_divよりも大きくない場合は、iとi2より小さくなるので、or x == i or x == i2を削除することは明らかです。ところで、if (x > max_div or x == i or x == i2):には余分な括弧は必要ありません：if x > max_div or x == i or x == i2:が有効です。
4. x == max_divの場合は、max_divがxの平方根より大きいため、breakが既に存在します。
5. **は+よりも優先されますので、max_div = i2 ** 0.5 + 1に簡略化してください。

だから今我々が持っている：

def is_prime(i): 
    max_div = i ** 0.5 + 1 
    for x in k: 
     if x >= max_div: 
      break 
    ... 

をこれは物事の愚かな方法です：ちょうどmax_divが上限である範囲を反復処理！範囲機能で使用できるようにmax_divをintに変換するだけです。 iが完璧な広場であるかどうか、そしてオフ・バイ・ワン・エラーがないかどうか、これが正しいことを自分自身に説得してください。その後、我々は持っている：

def is_prime(i): 
    max_div = int(i ** 0.5 + 1) 
    return not any(i % x == 0 for x in range(3, max_div, 2)) 

（私はあなたがそれに慣れていない場合にはgenerator expressionを使用しました）

：

def is_prime(i): 
    max_div = int(i ** 0.5 + 1) 
    for x in range(3, max_div, 2): 
     if i % x == 0: 
      return False 
    return True 

これはPythonで便利なリファクタリングすることができます一般的なパターンです

2つのトリックで、より簡潔にすることはできますが、読みにくくなる可能性があります。最初のインラインmax_divは1度しか使用されていないためです。代わりにanyのその後、あなたはallを使用して、ブール値としてint型を扱うことができます。

def is_prime(i): 
    return all(i % x for x in range(3, int(i ** 0.5 + 1), 2)) 

ここでは、したがって、（すべてのxためxで割ったときに、それはいくつかの非ゼロの残りを離れた場合の数が素数であることを言っていますall関数）をチェックする価値があります。これは、Python 0がFalseのようなもので、他のすべての数字がTrueのようになっているために機能します。

私の他の答えで述べたように、手動でペアをフォーマットする必要はありません。

printをステートメントとして使用していたので、あなたのタグの言うとおり、3ではなくPython 2を使用する必要があります。この場合、rangeのすべてのインスタンスを効率のためにxrangeに置き換えてください。

だから最後にそれだけだ：

n = 100 # upper limit number 

def is_prime(i): 
    return all(i % x for x in xrange(3, int(i ** 0.5 + 1), 2)) 

for i in xrange(3, n + 1, 2): 
    if is_prime(i) and is_prime(i + 2): 
     print (i, i + 2) 

私は、これはおそらくちょうどn = 100のために表示されませんが、私の他の答えは、より高速であることを確信していますが。最も目障りな問題は、iが素数である場合は、is_prime(i + 2)が呼び出され、ループの次の反復でis_prime(i)がちょうど計算されたように冗長になることです。これを改善するには、is_primeをセットでメモしてください。

Answer 3

私のコードを最適化して短くて高速にするにはどうすればよいですか？

ここで少し短くし、はるかに高速だふるいベースのアプローチです：100までの素数で作業する場合、任意のコードが実行します

def find_prime_pairs(n): 

    sieve = [True] * n 

    if n > 0: 
     sieve[0] = False 
     if n > 1: 
      sieve[1] = False 

    for number in range(2, int(n ** 0.5) + 1): 
     if sieve[number]: 
      for index in range(number * number, n, number): 
       sieve[index] = False 

    return [(a, b) for b, a in enumerate(range(0, n - 2), start=2) if sieve[a] and sieve[b]] 

print(*find_prime_pairs(100), sep='\n') 

USAGE

> python3 test.py 
(3, 5) 
(5, 7) 
(11, 13) 
(17, 19) 
(29, 31) 
(41, 43) 
(59, 61) 
(71, 73) 
> 

、それはパフォーマンスに課税するには小さすぎます。代わりに1000000（100万）を考えてみましょう。タイミングのために、ペアを印刷するのではなく、数えます。

@AlexHallが提供する最初の回答は、ペアを100万人までカウントする元のコードの2倍の時間を要します。彼の2番目の答えは元のコードよりも3倍長くなります。短いとは必ずしも速いとは限りません。あなたがそれを完全にテストするまで、どんな答えも信頼しないでください。

上記の篩ベースのコードは、元のコードより4倍高速で、15％小さくなっています。