By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,907 Members | 1,832 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,907 IT Pros & Developers. It's quick & easy.

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

P: 1
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.
Expand|Select|Wrap|Line Numbers
  1. def program(n): ## initializes
  2.     if n == 1: ## checks for special case of even prime 
  3.         print 2
  4.         return None 
  5.     counter = 1
  6.     index = 3
  7.     nthprime(n, counter, index) ## calls nthprime which takes n, counter index, as arguments 
  8.  
  9. def nthprime(n, counter, index):
  10.     if counter == n-1 and isprime(index) != None: ## test case
  11.         print index
  12.         return None
  13.     if isprime(index) != None: ## increments counter and sets index to next odd number if index is prime
  14.         counter = counter + 1   
  15.         index = index + 2
  16.  
  17.     else: index = index + 2  ## keeps counter the same and sets index to next odd number if index is not prime
  18.  
  19.     nthprime(n, counter, index)  ## calls nthprime with either the new counter and index or just the new index 
  20.  
  21. def isprime(x):
  22.  
  23.     index = 2 ## variable to check divisors
  24.     while index <= x**.5: ## loop condition of how many divisors to check 
  25.         if x%index == 0: ## if a remainder is found on first index return nothing 
  26.             return None
  27.  
  28.         else: index = index + 1  ## increment index and check again
  29.     return x ## no divisors found less than sqrt x, therefore number is prime
Dec 17 '10 #1
Share this Question
Share on Google+
1 Reply


Expert 100+
P: 624
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
Dec 17 '10 #2

Post your reply

Sign in to post your reply or Sign up for a free account.