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")
if n == 1:
print("This is not a Prime number")
else:
val1 = n // prime(n - 1)
if val1 == 0:
print("This is not a Prime number")
else:
print("This is a prime number")

5
Contributors
8
Replies
18
Views
6 Years
Discussion Span
Last Post by Thisisnotanid

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")
if n == 1:
print("Equals one, This is not a Prime number")
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")
else:
print("This is a prime number, else val1 == 0")

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

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

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

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

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

## use of True, not one

Edited by woooee: n/a

Hello,
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")
if n == 1:
print("Equals one, This is not a Prime number")
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")
else:
print("This is a prime number, else val1 == 0")

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

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

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

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

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

## use of True, not one

Hello,
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 by Gribouillis: n/a

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) ?

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.

Edited by Gribouillis: n/a

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))

Edited by brijesh8421: n/a

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")
if n == 1:
print("This is not a Prime number")
else:
val1 = n // prime(n - 1)
if val1 == 0:
print("This is not a Prime number")
else:
print("This is a prime number")

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!

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.