Forgive me for playing devil's advocate, but I spent many long hours on problem 1 in search of finding a way to define prime numbers, and some of the explanations listed above did not work (at least for me, for some reason). Please help me spot my error, and then I'll demonstrate a simpler solution I developed. When I employed the following:
dividend = 3
prime = [2,] #creates list of primes, 2 already included
while len(prime<=999): #lists start counting at zero
for i in range (2,dividend):
if dividend%i==o: #number is not prime
dividend+=1 #move to next step
else:
prime +=[dividend,] #add dividend to list prime
dividend += 1
print prime
By doing this, I only generated a list of odd numbers, not a list of prime numbers. For this reason, I don't believe that dividend%i==0 is a good test for finding a prime number. I believe my error was that once the computer ran a test for dividend%i==0 and found it false for any i, it immediately resorted to the "else" column and added the dividend to my list of primes. Therefore, a number like 15 (not prime) would be added to my list of primes because 15%2!=0. For those who had success using dividend%i==0 as a prime test, how did you avoid this?
What I ended up using instead (much simpler) was a mathematician's definition of prime, specifically the Fermat primality test:
if ((2**dividend)-2)%dividend==0:
prime += [dividend,] #number is prime
This prime check worked, which meant I only needed to control the flow until my prime list was created. I was able to generate the prime list, and my code is very short and simple. SO MUCH EASIER! Is this cheating? I didn't eliminate positive numbers as an initial step (as suggested on the assignment), but why should I have to if Fermat's test will do so for me automatically? Anyways, eliminating positive numbers could easily have been included, simply by testing for dividend%i==0 :)
As computer scientists, I don't think we should bang our heads on the wall devising new methods for defining prime numbers when mathematicians have already done the work for us? I consider this no different than importing a module, I suppose. But that's just my take on it. So... what am I missing?