Problem with returning prime number in a simple calculation program

[Steven D'Aprano]

On Sat, 03 Mar 2007 15:36:36 -0800, QHorizon wrote:

> Hello, I'm new to Python (I've learned everything up to iterators so
> far) and fairly new to Programming.  This would be my first real
> program:
> 
> #Coordinate Geometry (The whole program is not shown)
> 
> import math
> import sys
> 
> print "Welcome to the Coordinate Geometry Calculator!"
> print "Type 'terms' for a list of commands"
> 
> def main():

[snip big boring series of if...elif... statements]

You're eventually going to run into a run time recursion error if you run
that for long enough. Can you see why?

A better way to do a command loop is something like this:


def bad_command():
    # called when the user enters an unrecognized command
    print "Unknown command, please try again"

class QuitException(Exception):
    # used for exiting the loop
    pass


def main():
    # Make a "dispatch table" that maps the name of a command 
    # (as typed by the user) with a function to call.
    dispatcher = {'slope': do_slope,
                  'primes': do_primes,
                  'quit': do_quit,
                  # ... and more here
                 }
    try:
        # loop forever (until we jump out of it)
        while True:
            cmd = get_command_from_user()
            # you have to write get_command_from_user yourself
            func = dispatcher.get(cmd, bad_command)
            result = func()
            print result
    except QuitException:
        print "Goodbye, come again soon!"


Now you just need to define your individual functions do_slope, do_primes,
etc. The only "special" one is do_quit.

def do_quit():
    raise QuitException


Now let's look at the do_primes function. (You call it "prime".)

> def prime():
> 	num = input("Number ")

That's a good way to have malicious users do really, really really bad
things to your PC.

Safer is to do this:

num = int(raw_input("Number "))

> 	i = num - 1
> 	divcounter = 0
> 	while i > 1:
> 		if num % i != 0:
> 			divcounter += 1
> 			i -= 1

That's an inefficient algorithm, if it even works. I'm not sure that it
works, and I'm too lazy to find out :)


> 	if divcounter == num - 2:
> 		print num, "is a prime number"
> 	else:
> 		print num, "is not a prime number"

This will only work if divcounter happens to equal the original number
less two. If it equals something else, nothing will be printed.

Here's a simple algorithm to check if a number is prime.

# Warning: untested.
def do_primes():
    num = int(raw_input("Number ")
    if num <= 1:
        return "%n is not prime" % num
    if num == 2:
        return "%n is prime" % num
    elif num % 2 == 0:
        # even numbers other than 2 aren't prime
        return "%n is not prime" % num
    for i in range(3, num, 2):
        if num % i == 0:
            return "%n is not prime" % num
    return "%n is prime" % num


Now, this is deliberately not an efficient algorithm. There are things you
can do to make it more efficient, or you can re-write it completely.
The thing to remember is, don't PRINT the result, RETURN it. Your
do_primes() function should only calculate the result, and pass that
result up to the main loop for printing (or writing to a text file, or
emailing, or whatever).

Have fun!



-- 
Steven.