Segmentation fault in Prime Number generator

Question

I am aware the following isn't the fastest way of generating a list of primes however I posed myself the problem and before googling wrote the following program. It works fine for numbers < ~ 44,000 but then gives a segmentation fault when ran on my 2Ghz Core 2 Duo Macbook. I am not really interested in alternative methods at the moment but in why its giving me a seg fault.

The last prime it is able to calculate is 42751 before it dies saying 'Segmentation fault'.

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

You might be getting stack overflow from too many recusive calls on the stack. At 42751 you would have a 21375 depth function call stack. In such case, refining your method might actually be needed.

A handy little routine which will check primeness can be written like this (pseudocode):

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;

This method works because of the following:

1. If n is less than 2, it can't be prime
2. If n is 2 or 3 it must be prime
3. If n is not 2 or 3 but is divisible by either, it is not prime
4. All prime numbers aside from 2 and 3 can be written in the form 6k+1 or 6k-1. If a number is prime, it is not evenly divisible by any other prime number. Only need to check up until the square root of n because anything more than that definitely does not divide evenly into n.

Answer 2

Your program is using recursion. Every function call saves registers on to the stack and then jumps to the beginning of the function. Since your stack has a limited size, eventually you will run out of stack space. At this point you are you would be writing over memory you aren't supposed (or even allowed) to. Thus leading to a segmentation fault.

Answer 3

Setting a very large recursion limit and then recursing a bunch is one of the documented ways to crash the Python interpeter.

Essentially you're telling Python not to stop you if you recurse too far, and then you're recursing too far.

Answer 4

You're making a recursive call, counting up linearly by 2. CPython doesn't do tail call elimination, and (IIRC) it uses the C stack, so it's taking up some pretty serious stack space here.

I can't find the default stack size on 64-bit Mac OS (on 32-bit it appears to be 8MB) but it's definitely not infinite, and apparently not big enough to hold stack frames for every odd number up to 50,000.

Answer 5

My guess is you have run out of memory in the recursive part of your routine.

If you recode it as a loop incrementing x then you will find it goes further before crashing.