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

Help, determining if an input value is prime?

P: 15
I'm doing some reading in a python book and am doing one of the chapter exercises but I cant figure out how to get it to work and was hoping some of you python guru's could help out?

Heres description of the problem to be solved:

"A positive whole number n > 2 is prime if no number between 2 and the square root of n (inclusive) evenly divides n. Write a program that accepts a value of n as input and determines if the value is prime. If n is not prime, your program should quit as soon as it finds a value that evenly divides n."

Heres the code I have so far but it doesnt work very good...

Expand|Select|Wrap|Line Numbers
  1. def main():
  2.  
  3.     import math
  4.  
  5.     print "This program determines if a number you enter is prime or not.\n"
  6.     n = input ("Please enter a number greater than 1: ")
  7.  
  8.     n = abs(n)
  9.     i = 2
  10.     while i <= math.sqrt(n):
  11.         if n % i == 0:
  12.             print n, "is not a prime number"
  13.         i += 1
  14.     print n, "is a prime number!"
  15.  
  16. main()
  17.  
It tells me if a number is prime, but if it isnt prime it tells me it isnt, then tells me it is! LOL. I'm still a newbie when it comes to python...

I was able to get this far, but as far as "quitting as soon as it finds a value that evenly divides n." I have no clue how to do that...

Could someone please help?

Thanks a million!
Mar 14 '08 #1
Share this Question
Share on Google+
6 Replies


Expert 100+
P: 849
First off, do your importing at the top of the file, outside of functions as a general rule. There are times later you will need to change this, but for now just put them up there.

As to your extra message, that's because your code automatically executes the print statement after the while loop. A simple way to fix this is to use a boolean, which can have True or False values. Call it, say, found and default it to False, then if a non-prime is found, set it to True and at the end, if it's still False, print that it's prime.
Mar 14 '08 #2

P: 15
Okay, I tried to do what you suggested. Here is the updated code and the output, but its still doing something strange...

New code:
Expand|Select|Wrap|Line Numbers
  1. import math
  2.  
  3. def main():
  4.  
  5.     print "This program determines if a number you enter is prime or not.\n"
  6.     n = input ("Please enter a number greater than 1: ")
  7.     found = False
  8.     n = abs(n)
  9.     i = 2
  10.     while i <= math.sqrt(n):
  11.         if n % i == 0:
  12.             found = False
  13.             print n, "is not a prime number"
  14.         else:
  15.             found = True
  16.         i += 1
  17.  
  18.     if found == True:
  19.         print n, "is a prime number!"
  20.  
  21. main()
New result, prime number:
Please enter a number greater than 1: 37
37 is a prime number!


New result, not prime:
Please enter a number greater than 1: 9
9 is not a prime number


New result, large number:
Please enter a number greater than 1: 78999
78999 is not a prime number
78999 is not a prime number
78999 is not a prime number
78999 is a prime number!


What am I doing wrong?
Mar 14 '08 #3

Expert 100+
P: 849
There's a couple issues here: First, don't print before the loop is done, since if more than one divisor exists, it'll print multiple times. Second, the only time you need to change found is if you find a divisor.
Mar 14 '08 #4

bgeddy
P: 16
Also you really need to look into breaking out of the loop when a divisor is found. Maybe there is a simple statement to break out of a while loop ? When approaching a problem like this it helps to work the logic out in English (sometimes called pseudo code) first so for the loop part:

Expand|Select|Wrap|Line Numbers
  1. while divisor is less than or equal to the square root of number:
  2.         test if number mod divisor equals zero:
  3.               yes so set found to true and
  4.                 exit loop
  5.              else no so increment divisor
  6.                 continue loop
  7.  
  8. is found set to true ?
  9.     yes so print number " is not a prime"
  10.     else print numer "is a prime"
  11.  
Hopefully you can follow the logic of this (I'm not following any standards here). It should now be simple to translate this to python.

Check the problem decription, what's the smallest number you should be prompting for ?
Mar 14 '08 #5

raubana
P: 56
well, this would need two things:
1) a divisable list
2) the "check-if-it's-prime" part

the first part would require you to fin all the factors of the number
Expand|Select|Wrap|Line Numbers
  1. def divisable(x):
  2.    y=x
  3.    #this is here so you don't edit the real value
  4.  
  5.    list=[]
  6.    #this will hold all our factors
  7.  
  8.    number = 1
  9.    #this is the number we'll divide x by
  10.    while number<y:
  11.       if float(y)/float(number)==y/number: #this makes sure it is a whole number
  12.          list.insert(y/number)
  13.    return list
  14.  
so now we have a command that finds all the factors of a number, now we find out if it's prime. Now we all know that a prime number has only two factors (1 and itself), so all you have to do is find the length of the list to find if it's prime

Expand|Select|Wrap|Line Numbers
  1. while True: #this is an infinite loop
  2.     x=input("Tell me your number: ")
  3.     if len(divisable(x))==2:
  4.        print str(x)+"is prime."
  5.     else:
  6.        print str(x)+"is NOT prime."
  7.  
  8.     print
  9.  
  10.  
... so now we can run the program and you would get something like this:

Expand|Select|Wrap|Line Numbers
  1. >>>
  2. Tell me your number: 5
  3. 5 is prime.
  4.  
  5. Tell me your number: 12
  6. 12 is NOT prime.
  7.  
BTW this is not the most effective way, but it works!
Mar 14 '08 #6

bvdet
Expert Mod 2.5K+
P: 2,851
well, this would need two things:
1) a divisable list
2) the "check-if-it's-prime" part

the first part would require you to fin all the factors of the number
Expand|Select|Wrap|Line Numbers
  1. def divisable(x):
  2.    y=x
  3.    #this is here so you don't edit the real value
  4.  
  5.    list=[]
  6.    #this will hold all our factors
  7.  
  8.    number = 1
  9.    #this is the number we'll divide x by
  10.    while number<y:
  11.       if float(y)/float(number)==y/number: #this makes sure it is a whole number
  12.          list.insert(y/number)
  13.    return list
  14.  
so now we have a command that finds all the factors of a number, now we find out if it's prime. Now we all know that a prime number has only two factors (1 and itself), so all you have to do is find the length of the list to find if it's prime
All you need is integer math. You can use the modulo operator to determine if variable x is divisible by number. Also there is no need in checking number when it exceeds the square root of x. It is not a good idea to use a variable name that is the same as a built-in Python function (list).

Following is the function I use to calculate the positive proper divisors of a given number:
Expand|Select|Wrap|Line Numbers
  1. def proper_divisors(num):
  2.     if not num%2:
  3.         start, stride = 2, 1
  4.     else:
  5.         start, stride = 3, 2
  6.     factlist = [1,]
  7.     for i in xrange(start, int(num**0.5)+1, stride):
  8.         if not num%i:
  9.             factlist.append(i)
  10.             if not i*i == num:
  11.                 factlist.append(num/i)
  12.     factlist.sort()
  13.     return factlist
Example:
Expand|Select|Wrap|Line Numbers
  1. >>> proper_divisors(39438620)
  2. [1, 2, 4, 5, 10, 13, 20, 26, 52, 65, 130, 260, 151687, 303374, 606748, 758435, 1516870, 1971931, 3033740, 3943862, 7887724, 9859655, 19719310]
  3. >>> 
If all you want to do is check if a number is prime, you can do the same as above without building a list.
Expand|Select|Wrap|Line Numbers
  1. def is_prime(n):
  2.     if n < 2:
  3.         return False
  4.     elif n == 2:
  5.         return True
  6.     elif not n%2:
  7.         return False
  8.     for i in xrange(3, int(n**0.5)+1, 2):
  9.         if not n%i:
  10.             return False
  11.     return True
Then all you need to do is check for True or False.
Expand|Select|Wrap|Line Numbers
  1. def main():
  2.     print "This program determines if a number you enter is prime or not.\n"
  3.     n = input ("Please enter a number greater than 1: ")
  4.     if is_prime(n):
  5.         print '%d is a prime number.' % n
  6.     else:
  7.         print '%d is not a prime number.' % n
  8.  
  9. main()
Mar 14 '08 #7

Post your reply

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