Python - Recursive Prime Number function

Question

leazell 0 Newbie Poster

13 Years Ago

I am trying to create a simple recursive prime number function.
I am not sure why this is not working. I originally was using remainder division but changed it to integer division.

**** if n ==0: # This runs infinitely,
The recursive call does not seem to roll down.

Output looks like this for the prime number 5 and the not prime number 4
======================
enter a number to check for prime: 5
This is not a Prime number
This is a prime number
This is a prime number
This is a prime number
This is a prime number
The number 5 is True.
==================================
Would you like to check another number for prime? y
enter a number to check for prime: 4
This is not a Prime number
This is a prime number
This is a prime number
This is a prime number
The number 4 is True.
Would you like to check another number for prime?
=========================================

def prime(n):
    if n == 0:
        print("This is not a Prime number")
        answer = 0
    if n == 1:
        print("This is not a Prime number")
        answer = 1
    else:
        val1 = n // prime(n - 1)
        if val1 == 0:
            print("This is not a Prime number")
            answer = False
        else:
            print("This is a prime number")
            answer = True
        
    return answer

python

5 Contributors
8 Replies
6K Views
2 Weeks Discussion Span
Latest Post 13 Years Ago Latest Post by Thisisnotanid

woooee 814 Nearly a Posting Maven

13 Years Ago

Add a little more to the print statements to tell you where you are.

def prime(n):
    print "-"*30
    print "starting prime with n =", n
    if n == 0:
        print("Equals zero, This is not a Prime number")
        answer = 0
    if n == 1:
        print("Equals one, This is not a Prime number")
        answer = 1
    else:
        val1 = n // prime(n - 1)
        print "val1 = n // prime(n - 1)", val1
        if val1 == 0:
            print("This is not a Prime number, if val1 == 0")
            answer = False
        else:
            print("This is a prime number, else val1 == 0")
            answer = True
 
    return answer

Also add a counter for testing to limit the recursion.

def prime(n, limit):


    else:
        limit += 1
        if limit < 10:
            val1 = n // prime(n - 1, limit)

Also, you should use either True/False or 0/1 for "answer" and not some combination.

def prime(n):
    print "-"*30
    print "starting prime with n =", n
    if n == 0:
        print("Equals zero, This is not a Prime number")

        ## zero = False
        answer = 0

    if n == 1:
        print("Equals one, This is not a Prime number")

        ## one = True but you print that it is not prime
        answer = 1 

        if val1 == 0:
            print("This is not a Prime number, if val1 == 0")

            ## use of False, not zero
            answer = False
        else:
            print("This is a prime number, else val1 == 0")

            ## use of True, not one
            answer = True

Edited 13 Years Ago by woooee because: n/a

Gribouillis 1,391 Programming Explorer

13 Years Ago

Hello,
Thank you for your comments!
Upon testing I notice that 4 still returns - it is a prime number.
This is not correct. The numbers 2,3,5,7,11,13 and 17 and 19 are prime, the ones I skip here are not.
Can you help me come up with a solution to accurately assign either Prime (True) or Not Prime (False)to the number(n).
Thank you

Can you explain your algorithm (independently of the code) ?

Edited 13 Years Ago by Gribouillis because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

leazell 0 Newbie Poster · Answer 1 · 2010-12-13T11:00:50+00:00

Hello,
Thank you for your comments!
Upon testing I notice that 4 still returns - it is a prime number.
This is not correct. The numbers 2,3,5,7,11,13 and 17 and 19 are prime, the ones I skip here are not.

Can you help me come up with a solution to accurately assign either Prime (True) or Not Prime (False)to the number(n).
Thank you

Add a little more to the print statements to tell you where you are.

def prime(n):
    print "-"*30
    print "starting prime with n =", n
    if n == 0:
        print("Equals zero, This is not a Prime number")
        answer = 0
    if n == 1:
        print("Equals one, This is not a Prime number")
        answer = 1
    else:
        val1 = n // prime(n - 1)
        print "val1 = n // prime(n - 1)", val1
        if val1 == 0:
            print("This is not a Prime number, if val1 == 0")
            answer = False
        else:
            print("This is a prime number, else val1 == 0")
            answer = True
 
    return answer

Also add a counter for testing to limit the recursion.

def prime(n, limit):


    else:
        limit += 1
        if limit < 10:
            val1 = n // prime(n - 1, limit)

Also, you should use either True/False or 0/1 for "answer" and not some combination.

def prime(n):
    print "-"*30
    print "starting prime with n =", n
    if n == 0:
        print("Equals zero, This is not a Prime number")

        ## zero = False
        answer = 0

    if n == 1:
        print("Equals one, This is not a Prime number")

        ## one = True but you print that it is not prime
        answer = 1 

        if val1 == 0:
            print("This is not a Prime number, if val1 == 0")

            ## use of False, not zero
            answer = False
        else:
            print("This is a prime number, else val1 == 0")

            ## use of True, not one
            answer = True

leazell 0 Newbie Poster · Answer 2 · 2010-12-13T12:38:38+00:00

Prime Number Recipe
1. n is a positive integer
2. if n is zero, it is NOT a Prime Number
3. if n is 1, it is NOT a Prime Number
4. A prime number can only be divided evenly by itself and 1(one).
5. See if n can be evenly divided by numbers less than itself (other than itself
and one).
The recursive call needs to address going through the downward division
Exmple 6 = 6 // 5 = 1.2ish, 6 // 4 = 1.4ish, 6 // 3 = 2, 6 // 2 = 3,
This number is NOT a Prime Number

Can you explain your algorithm (independently of the code) ?

Gribouillis 1,391 Programming Explorer Team Colleague · Answer 3 · 2010-12-13T15:15:26+00:00

Prime Number Recipe
1. n is a positive integer
2. if n is zero, it is NOT a Prime Number
3. if n is 1, it is NOT a Prime Number
4. A prime number can only be divided evenly by itself and 1(one).
5. See if n can be evenly divided by numbers less than itself (other than itself
and one).
The recursive call needs to address going through the downward division
Exmple 6 = 6 // 5 = 1.2ish, 6 // 4 = 1.4ish, 6 // 3 = 2, 6 // 2 = 3,
This number is NOT a Prime Number

No recursion is needed: you need to know if n can be divided by smaller numbers, but you don't need to know if these smaller numbers are primes. So you don't have to call your function recursively.

brijesh8421 0 Newbie Poster · Answer 4 · 2010-12-27T23:43:19+00:00

import math
print ("You want prime till which number??")

a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):

e = c % b
e = int(e)
if (e == 0):
x = x+1

if (x == 0):
print("%d is prime number" % c)
count = count + 1

print("Total number of prime till %d is %d" % (a,count))

Thisisnotanid 0 Junior Poster in Training · Answer 5 · 2010-12-28T00:47:15+00:00

I am trying to create a simple recursive prime number function.
I am not sure why this is not working. I originally was using remainder division but changed it to integer division.
**** if n ==0: # This runs infinitely,
The recursive call does not seem to roll down.
Output looks like this for the prime number 5 and the not prime number 4
======================
enter a number to check for prime: 5
This is not a Prime number
This is a prime number
This is a prime number
This is a prime number
This is a prime number
The number 5 is True.
==================================
Would you like to check another number for prime? y
enter a number to check for prime: 4
This is not a Prime number
This is a prime number
This is a prime number
This is a prime number
The number 4 is True.
Would you like to check another number for prime?
=========================================
def prime(n):
    if n == 0:
        print("This is not a Prime number")
        answer = 0
    if n == 1:
        print("This is not a Prime number")
        answer = 1
    else:
        val1 = n // prime(n - 1)
        if val1 == 0:
            print("This is not a Prime number")
            answer = False
        else:
            print("This is a prime number")
            answer = True
        
    return answer

As far as I can see, it's a logic error. You've inadvertently designed the program to keep iterating till any value entered is reduced to 1. The python command line greatly helps in situations like this one. The program does the following:

Let's say you enter 5. The parameter, n, doesn't equal either 0 or 1 so the first else statement kicks in. The program tries to assign a value to 'val1', but it needs prime(n-1) to do that. So it calls the function again. But before it starts doing that, it checks the if-else clause you have under your first else statement. Since 'val1' doesn't have a value, the second else clause is invoked and it prints, "This is a prime number." and assigns 'answer' the boolean value True. Now the function is called again with the new value for the parameter n = 4. The same thing happens again. It calls 4 // prime(3) but prime(3) is not defined, it prints "This is a prime number." The above keeps happening till 2 // prime(1) is called. Now since n = 1, it assigns 'answer' the value 1, which acts as a boolean value of True and the function exits returning True. That's why you're getting composite numbers to be listed as primes.

I don't know how the rest of your program is written, and maybe that explains what I haven't been able to account for here. Of course, I may be wrong and what I've described is not the issue (especially considering I'm relatively new to this myself :) ). However, I've written code that might prove helpful:

n1 = int(raw_input("Please enter an integer to test for primality: "))
l1 = n1 - 1
def recPrime(n, l):
	if n < 2:
		print 'Not prime.'
	else:
		if n % l == 0:
			print 'Not prime.'
		elif n % l != 0 and l != 2:
			recPrime(n, l - 1)
		elif n % l != 0 and l == 2:
			print 'Prime!'

recPrime(n1, l1)

I hope that helps!

Thisisnotanid 0 Junior Poster in Training · Answer 6 · 2010-12-28T04:38:34+00:00

Also, I forgot to mend the code to account for 2. The program returns "Not prime.' for that value, but that's easily fixable. :)