私はPythonのコツをつかみ始めているので、projecteuler.netのいくつかの問題について新しく習得したPythonスキルをテストし始めています。
とにかく、ある時点で、数'n'までのすべての素数のリストを取得する関数を作成することになりました。
関数のatmは次のようになります。
def primes(n):
"""Returns list of all the primes up until the number n."""
# Gather all potential primes in a list.
primes = range(2, n + 1)
# The first potential prime in the list should be two.
assert primes[0] == 2
# The last potential prime in the list should be n.
assert primes[-1] == n
# 'p' will be the index of the current confirmed prime.
p = 0
# As long as 'p' is within the bounds of the list:
while p < len(primes):
# Set the candidate index 'c' to start right after 'p'.
c = p + 1
# As long as 'c' is within the bounds of the list:
while c < len(primes):
# Check if the candidate is divisible by the prime.
if(primes[c] % primes[p] == 0):
# If it is, it isn't a prime, and should be removed.
primes.pop(c)
# Move on to the next candidate and redo the process.
c = c + 1
# The next integer in the list should now be a prime,
# since it is not divisible by any of the primes before it.
# Thus we can move on to the next prime and redo the process.
p = p + 1
# The list should now only contain primes, and can thus be returned.
return primes
気になることが1つありますが、問題なく動作しているようです。コードにコメントしている間、この部分は突然外れたように見えました：
# Check if the candidate is divisible by the prime.
if(primes[c] % primes[p] == 0):
# If it is, it isn't a prime, and should be removed from the list.
primes.pop(c)
# Move on to the next candidate and redo the process.
c += 1
候補が素数で割り切れない場合は、「c+1」にある次の候補を調べます。問題ありません。
ただし、候補が素数で割り切れる場合は、最初にそれをポップしてから、「c+1」にある次の候補を調べます。ポップした後の次の候補は「c+1」ではなく「c」にあることに気づきました。「c」でポップした後、次の候補はそのインデックスに「分類」されるからです。
次に、ブロックは次のようになるはずだと思いました。
# If the candidate is divisible by the prime:
if(primes[c] % primes[p] == 0):
# If it is, it isn't a prime, and should be removed from the list.
primes.pop(c)
# If not:
else:
# Move on to the next candidate.
c += 1
上記のブロックは私にはもっと正しいように見えますが、なぜ元の作品がどうやらうまく機能したのか疑問に思います。
だから、ここに私の質問があります：
素数ではないことが判明した候補をポップした後、私の元のコードのように、次の候補は同じ素数で割り切れないと仮定できますか？
もしそうなら、それはなぜですか？
提案された「安全な」コードは、「安全でない」コードでスキップされた候補に対して不必要なチェックを行うだけでしょうか？
PS：
上記の仮定をアサーションとして「unsafe」関数に書き込んでみて、n=100000でテストしました。問題は発生しませんでした。変更されたブロックは次のとおりです。
# If the candidate is divisible by the prime:
if(primes[c] % primes[p] == 0):
# If it is, it isn't a prime, and should be removed.
primes.pop(c)
# If c is still within the bounds of the list:
if c < len(primes):
# We assume that the new candidate at 'c' is not divisible by the prime.
assert primes[c] % primes[p] != 0
# Move on to the next candidate and redo the process.
c = c + 1