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. -- http://mail.python.org/mailman/listinfo/python-list