С тех пор как я начинаю пользоваться Python, я начинаю тестировать свои недавно приобретенные навыки Python по некоторым проблемам на projecteuler.net.
В любом случае, в какой-то момент я закончил создание функции для получения списка всех простых чисел вплоть до числа "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
Кажется, что все нормально, хотя одна вещь меня беспокоит. Комментируя код, эта часть внезапно показалась немой:
# 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'. Нет проблем с этим.
Однако, если кандидат IS делится на простое, мы сначала выкладываем его, а затем исследуем следующего кандидата, расположенного в '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:
Я пробовал написать вышеприведенное предположение как утверждение в "небезопасную" функцию и протестировать ее с 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
