0

I have edited a piece of code which gives feedback for prime numbers on a large scale. If the number is Prime it will result with a two digit number that ends in zero and it will show two of the same numbers. For composite a number it will show two numbers that don't end in ZERO. You would input the number in this fashion for a composite input range(2^8-2, 2^8)--output__54 54 or for a prime input range(2^7-2, 2^7)--output is __30 30

However I'm getting a recursive error. Is there a way to rewrite the code, so that it does not use recursion or is there a work around the recursion. I have tried increasing the sys overhead, but it did not work.

I noticed the recursion error when I tried 11.

Here is the code if someone can help me code it so recursion does not come up?

 def isPrime(n):

     isPrime = True

     def is_divisible(n,divisor):
         if n<(divisor-1)*divisor: return False
         if n%divisor==0: return True
         else:
             divisor += 1
             return is_divisible(n,divisor)

     if n==2:
         isPrime = True
     elif is_divisible(n,divisor=2):
         isPrime = False
     return isPrime

 def getNumPrimes(n):
     if n <= 2:
         return 0
     else:
         return isPrime(n-1) + getNumPrimes(n-1)
    
 for n in range(2**11-2,2**11):
     print(getNumPrimes(n))
stellarwest
  • 13
  • 2

1 Answers1

0

You could use the iterative variation of your algorithm. Instead of using recursion for both is_divisible() and getNumPrimes(), you can start from the bottom and work your way up.

There are a bunch of different ways to compute the number of primes less than or equal to a given number, this post benchmarks a handful of them that are written in python. Here's a paste of the quickest one:

def prime_count(n):
    """Counts number of prime numbers from 0 to n (inclusive)."""
    count = 0
    sieve = [True] * (n + 1)
    for p in range(2, n):
        if sieve[p]:
            count += 1
            for i in range(p, n + 1, p):
                sieve[i] = False
    return count

Alternatively, if you don't want to edit the code, you can increase the recursion limit in python using the sys module (although, there might be some unintended consequences, so proceed with caution):

import sys
sys.getrecursionlimit()
>>> 3000

getNumPrimes(6000)
>>> RecursionError: maximum recursion depth exceeded in comparison

sys.setrecursionlimit(10000)
getNumPrimes(6000)
>>> 783
Jay Mody
  • 3,727
  • 1
  • 11
  • 27
  • Hi Jay, I did get to see 11 and it was 309 309, but it bombed out at 31, so thanks tho, maybe a rewrite of the code, its a shame cause, I think this code may indicate large primes. – stellarwest Dec 22 '20 at 03:56
  • I heard that if this code is iterative that it would work but I'm not that advanced a python. – stellarwest Dec 22 '20 at 04:03
  • @stellarwest updated, my post, see the iterative solution posted – Jay Mody Dec 22 '20 at 04:17