Ошибка сегментации в генераторе простых чисел

Question

Я знаю, что следующее не является самым быстрым способом создания списка простых чисел, однако я поставил перед собой проблему, и перед поиском в Google написал следующую программу. Он работает нормально для чисел <~ 44 000, но затем выдает ошибку сегментации при запуске на моем 2 ГГц Core 2 Duo Macbook. В настоящий момент я не очень заинтересован в альтернативных методах, но в том, почему он дает мне ошибку. </p>

Последнее простое число, которое он может рассчитать, - это 42751, прежде чем он умрет, сказав «Ошибка сегментации».

from sys import argv, exit, setrecursionlimit

def isPrime(no, halfNo, x = 3):

  # if counted through and all numbers from 3 too x are not factors is prime
  if x > halfNo:
    print no
    return 1

  # is x a factor?
  if no % x == 0:
    return 0
  else:
    isPrime(no, halfNo, x + 2)

path, limLow, limHigh = argv

limLow = int(limLow)
limHigh = int(limHigh)

setrecursionlimit(limHigh)

# negitive numbers, 0 and 1 are not primes so answer invalid
if limLow < 2:
  exit('Invalid input');

# if lower limit is even its not prime so increase by 1
if limLow % 2 == 0:
  limLow += 1

while (limLow <= limHigh):
  isPrime(limLow, limLow / 2)
  limLow += 2

Answer 1

Возможно, вы переполняете стек из-за слишком большого количества рекурсивных вызовов в стеке.На 42751 у вас будет стек вызовов функций глубиной 21375.В таком случае может потребоваться уточнение вашего метода.

Удобная небольшая процедура, которая проверяет простоту, может быть написана так (псевдокод):

if n < 2 return false;
if n == 2 or n == 3 return true;
if n % 2 == 0 return false;
if n % 3 == 0 return false;
for (i = 6; i < sqrt(n); i += 6) {
  if (n % (i - 1) == 0) return false;
  if (n % (i + 1) == 0) return false;
}
return true;

Этот метод работает из-заследующее:

1. Если n меньше 2, оно не может быть простым
2. Если n равно 2 или 3, оно должно быть простым
3. Если n не является2 или 3, но делится на любое из них, оно не простое
4. Все простые числа, кроме 2 и 3, можно записать в виде 6k + 1 или 6k-1.Если число простое, оно не делится поровну на любое другое простое число.Нужно только проверить до получения квадратного корня из n, потому что что-то большее, чем это, определенно не делится равномерно на n.

Answer 2

Ради потомков код, который я написал в конце, который исправил ошибку, был следующим:

import sys

def isPrime( no ):
  sqrt = round(no**0.5);
  # if counted through and all numbers from 3 too x are not factors is prime
  if no % 2 == 0 or no % 3 == 0:
    return False
  for x in range(6, int(sqrt), 6):
    if no % (x - 1) == 0:
      return False
    if no % (x + 1) == 0:
      return False
  return True

def primesInRange(limLow, limHigh):
   # negitive numbers, 0 and 1 are not primes so answer invalid
  if limLow < 2:
    raise ValueError('Lower limit must be 2 or more')
  # if lower limit is even its not prime so increase by 1
  if limLow % 2 == 0:
    limLow += 1
  primes = []
  while (limLow <= limHigh):
    if isPrime(limLow): primes.append(limLow)
    limLow += 2
  return primes


def main():
  limLow = int(sys.argv[1])
  limHigh = int(sys.argv[2])
  print primesInRange(limLow, limHigh)

if __name__ == '__main__':
  main()

Answer 3

Полагаю, вам не хватило памяти в рекурсивной части вашей подпрограммы.

Если вы перекодируете ее как цикл, увеличивающий x, то вы обнаружите, что он идет дальше до сбоя.

Answer 4

Вы делаете рекурсивный вызов, считая линейно на 2. CPython не выполняет удаление хвостовых вызовов, и (IIRC) он использует стек C, поэтому он занимает здесь довольно серьезное пространство стека.

Я не могу найти размер стека по умолчанию в 64-битной Mac OS (в 32-битной версии он выглядит как 8 МБ), но он определенно не бесконечен и, очевидно, недостаточно велик для хранения кадров стека для каждого нечетного числа вплоть до 50000.

Answer 5

Установка очень большого предела рекурсии, а затем повторение группы - это один из документированных способов аварийного завершения работы интерпретатора Python.

По сути, вы говорите Python не останавливать вас, еслизацикливайтесь слишком далеко, и затем вы возвращаетесь слишком далеко.

Answer 6

Ваша программа использует рекурсию.Каждый вызов функции сохраняет регистры в стеке, а затем переходит к началу функции.Поскольку ваш стек имеет ограниченный размер, в конечном итоге вам не хватит места в стеке.В этот момент вы будете перезаписывать память, которую вы не должны (или даже не имеете) делать.Это приводит к ошибке сегментации.