Программа не работает быстрее, чем ожидалось, при проверке гораздо меньшего количества чисел для поиска простых чисел

Question

Я сделал программу для поиска простых чисел ниже заданного числа.

      number = int(input("Enter number: "))
prime_numbers = [2]  # First prime is needed.
for number_to_be_checked in range(3, number + 1):  
    square_root = number_to_be_checked ** 0.5
    for checker in prime_numbers:  # Checker will become 
           # every prime number below the 'number_to_be_checked'
           # variable because we are adding all the prime numbers 
           # in the 'prime_numbers' list.
        if checker > square_root:
            prime_numbers.append(number_to_be_checked)
            break
        elif number_to_be_checked % checker == 0:
            break
print(prime_numbers)

Эта программа проверяет каждое число ниже числа, заданного в качестве входных данных. Но простые числа имеют только форму. Поэтому вместо проверки всех чисел я определил генератор, который генерирует все числа формы ниже числа, заданного в качестве входных данных. (Я добавил 3 также вprime_numbersсписок при инициализации его как2,3не может быть в форме6k ± 1)

      def potential_primes(number: int) -> int:
    """Generate the numbers potential to be prime"""
    # Prime numbers are always of the form 6k ± 1.
    number_for_function = number // 6
    for k in range(1, number_for_function + 1):
        yield 6*k - 1
        yield 6*k + 1

Очевидно, что программа должна была работать намного быстрее, потому что я проверяю гораздо меньше чисел. Но, как ни странно, программа работает медленнее, чем раньше. Что может быть причиной этого?

Answer 1

Из каждых шести чисел три четные, а одно кратно 3. Два других взаимно просты по 6, поэтому потенциально являются простыми:

      6k+0    6k+1    6k+2    6k+3    6k+4    6k+5
even            even            even
3x                      3x

Для трех четных ваша проверка простоты использует только одно деление (на 2), а для четвертого числа — два деления. В целом, пять разделений, которых вы пытаетесь избежать.

Но каждый вызов генератора тоже имеет свою цену. Если вы просто замените вызов наrangeс призывом создать свой генератор, но оставить другой код как есть (*), вы не реализуете весь потенциал экономии.

Почему? Потому что (*) если это так, хотя сейчас вы действительно проверяете только 1/3 чисел, вы все равно проверяете каждое из них на 2 и 3. Без необходимости. И, видимо, стоимость использования генератора слишком высока.

Смысл этого метода, известного как колесная факторизация, состоит в том, чтобы не проверять 6- взаимно простые (в данном случае) числа простыми числами, которые, как уже известно, не являются их делителями, по построению .

Таким образом, вы должны начать, например, сprime_numbers = [5,7]и используйте его в своем цикле проверки делимости, а не все простые числа, которые начинаются с 2 и 3, которые вам не нужны.

Answer 2

Один из способов использовать идею 6n±1 — чередовать размеры шагов в основном цикле, делая шаг 2, а затем 4. Мой Python не очень хорош, так что это псевдокод:

      function listPrimes(n)
  // Deal with low numbers.
  if (n < 2) return []
  if (n = 2) return [2]
  if (n = 3) return [2, 3]

  // Main loop
  primeList ← [2, 3]
  limit ← 1 + sqrt(n) // Calculate square root once.
  index ← 5           // We have checked 2 and 3 already.
  step ← 2            // Starting step value: 5 + 2 = 7.
  
  while (index <= limit) {
    if (isPrime(index)) {
      primeList.add(index)
    }
    index ← index + step
    step ← 6 - step      // Alternate steps of 2 and 4
  }
  
  return primeList
end function