Why does my code to find primes stop working after prime 300?

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • joseph terzi
    New Member
    • Dec 2010
    • 1

    #1

    Why does my code to find primes stop working after prime 300?

    I am trying to use recursion to calculate the nth prime. It works up until i believe around 300 when the interpreter says "maximum recusrion depth exceeded." Here is the code i wrote.
    Code:
    def program(n): ## initializes
        if n == 1: ## checks for special case of even prime 
            print 2
            return None 
        counter = 1
        index = 3
        nthprime(n, counter, index) ## calls nthprime which takes n, counter index, as arguments 
    
    def nthprime(n, counter, index):
        if counter == n-1 and isprime(index) != None: ## test case
            print index
            return None
        if isprime(index) != None: ## increments counter and sets index to next odd number if index is prime
            counter = counter + 1   
            index = index + 2
        
        else: index = index + 2  ## keeps counter the same and sets index to next odd number if index is not prime
        
        nthprime(n, counter, index)  ## calls nthprime with either the new counter and index or just the new index 
        
    def isprime(x):
        
        index = 2 ## variable to check divisors
        while index <= x**.5: ## loop condition of how many divisors to check 
            if x%index == 0: ## if a remainder is found on first index return nothing 
                return None
            
            else: index = index + 1  ## increment index and check again
        return x ## no divisors found less than sqrt x, therefore number is prime
    Last edited by bvdet; Dec 20 '10, 04:59 PM. Reason: Add code tags
  • dwblas
    Recognized Expert Contributor
    • May 2008
    • 626

    #2
    There is no reason to use recursion for prime numbers. Generally a for() or while() loop is used.
    1. Number is 3 or greater and not an even number
    2. For loop from 3 to square root + 1 of the number, step=2 to eliminate division by even numbers
    3. If division results in no remainder, exit or return from the function

    Comment

    Working...