prime number

[Dale Hagglund]

    lostinpython> I'm having trouble writing a program that figures
    lostinpython> out a prime number.  Does anyone have an idea on how
    lostinpython> to write it?  

[I can't quite tell from your posts what your level of programming
knowledge is, so I've aimed low.  If this was wrong, please accept my
apologies. --rdh]

It's not quite clear precisely what the problem is. Do you want to
find all primes less than some number N, or find the prime
factorization of some input number, or something else altogether?  Are
there any other constraints?  Ie, does the program have to be
recursive?

I'm going to assume that you want to find all primes less than N, and
that are no constraints on the form of the program.  

First, pretend you have a function called "is_prime".  It will look
something like this:

        def is_prime(n):
            # return True if n is prime, False otherwise
            # magic goes here

If we had this function, the our main program would look something
like this:

        N = 20
        for n in range(1, N+1):
            if is_prime(n):
               print n

NOTE: range(1,N+1) returns a list of numbers from 1 to N inclusive.

The question now is how to fill in the missing part of is_prime.  In
your original post, you noted that n>2 is prime if no number between 2
and sqrt(n) inclusive divides into n evenly.

This tells us that we have to test a list of possible factors for
divisibility into n.  Ignoring, for a little while, how we figure out
the possible factors, we can now expand is_prime as follows:

        def is_prime(n):
            # return 1 if n is prime, 0 otherwise
            from math import sqrt
            for i in possible_factors:
                # if i divides n, n isn't prime
            # if no i divided into n, ie, we fell out of the loop, 
            # n is prime

The possible factor i divides into n if n % i == 0.  Once we've
decided that n is or isn't prime, we can just return True or False
respectively.  Adding these details:

        def is_prime(n):
            # return 1 if n is prime, 0 otherwise
            from math import sqrt
            for i in possible_factors:
                if n % i == 0:
                    return True
            return False   

The final step is to figure out the list of possible factors.  By the
definition, this is the list of integers from 2 to the integer value
of sqrt(n), inclusive.  To get this list, we can use the range
function again, assuming that sqrt(n) to compute the square root for
us.  The list of possible factors is given by

        range(2, int(sqrt(n)) + 1)

The final trick to is to get the definition of sqrt.  It turns out
that this function is defined in the math module.  Adding the bit of
syntax needed to access the sqrt function, we have:

        def is_prime(n):
            # return 1 if n is prime, 0 otherwise
            from math import sqrt
            for i in range(2, int(sqrt(n)) + 1):
                if n % i == 0:
                    return False
            return True

Put together with the main program above, this will print out a list
as follows:

        1
        2
        3
        5
        7
        11
        13
        17
        19

However, there's a slight problem here.  By definition, 1 is not a
prime.  We could fix this a couple of ways.  Either we could change
the main program not to start its range with 1, or we can fix
is_prime.  The latter is simple:

        def is_prime(n):
            # return 1 if n is prime, 0 otherwise
            from math import sqrt
            if n == 1:
                return False
            for i in range(2, int(sqrt(n)) + 1):
                if n % i == 0:
                    return False
            return True

Another algorithm mentioned in the followups to your posting is the
Sieve of Eratosthenes, named for its ancient Greek discoverer.  You
can find a description of the Sieve in many places on the web.  Trying
to implement it might be a good next step.

Dale.