Help, determining if an input value is prime?

[sigkill9]

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

def main():
 
    import math
 
    print "This program determines if a number you enter is prime or not.\n"
    n = input ("Please enter a number greater than 1: ")
 
    n = abs(n)
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            print n, "is not a prime number"
        i += 1
    print n, "is a prime number!"
 
main()
 

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!

[Laharl]

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.

[sigkill9]

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

New code:

import math
 
def main():
 
    print "This program determines if a number you enter is prime or not.\n"
    n = input ("Please enter a number greater than 1: ")
    found = False
    n = abs(n)
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            found = False
            print n, "is not a prime number"
        else:
            found = True
        i += 1
 
    if found == True:
        print n, "is a prime number!"
 
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?

[Laharl]

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.

[bgeddy]

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:

while divisor is less than or equal to the square root of number:
        test if number mod divisor equals zero:
              yes so set found to true and
                exit loop
             else no so increment divisor
                continue loop
 
is found set to true ?
    yes so print number " is not a prime"
    else print numer "is a prime"
 

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 ?

[raubana]

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

def divisable(x):
   y=x
   #this is here so you don't edit the real value
 
   list=[]
   #this will hold all our factors
 
   number = 1
   #this is the number we'll divide x by
   while number<y:
      if float(y)/float(number)==y/number: #this makes sure it is a whole number
         list.insert(y/number)
   return list
 

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

while True: #this is an infinite loop
    x=input("Tell me your number: ")
    if len(divisable(x))==2:
       print str(x)+"is prime."
    else:
       print str(x)+"is NOT prime."
 
    print
 
 

... so now we can run the program and you would get something like this:

>>>
Tell me your number: 5
5 is prime.
 
Tell me your number: 12
12 is NOT prime.
 

BTW this is not the most effective way, but it works!

[bvdet]

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

def divisable(x):
   y=x
   #this is here so you don't edit the real value
 
   list=[]
   #this will hold all our factors
 
   number = 1
   #this is the number we'll divide x by
   while number<y:
      if float(y)/float(number)==y/number: #this makes sure it is a whole number
         list.insert(y/number)
   return list
 

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:

def proper_divisors(num):
    if not num%2:
        start, stride = 2, 1
    else:
        start, stride = 3, 2
    factlist = [1,]
    for i in xrange(start, int(num**0.5)+1, stride):
        if not num%i:
            factlist.append(i)
            if not i*i == num:
                factlist.append(num/i)
    factlist.sort()
    return factlist

Example:

>>> proper_divisors(39438620)
[1, 2, 4, 5, 10, 13, 20, 26, 52, 65, 130, 260, 151687, 303374, 606748, 758435, 1516870, 1971931, 3033740, 3943862, 7887724, 9859655, 19719310]
>>> 

If all you want to do is check if a number is prime, you can do the same as above without building a list.

def is_prime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    elif not n%2:
        return False
    for i in xrange(3, int(n**0.5)+1, 2):
        if not n%i:
            return False
    return True

Then all you need to do is check for True or False.

def main():
    print "This program determines if a number you enter is prime or not.\n"
    n = input ("Please enter a number greater than 1: ")
    if is_prime(n):
        print '%d is a prime number.' % n
    else:
        print '%d is not a prime number.' % n
 
main()