[Tutor] help with prime number program

[Glen Wheeler]

From: "Norman Silverstone" <norman at littletank.org>
> On Mon, 2005-10-31 at 06:12 -0500, Kent Johnson wrote:
>> Norman Silverstone wrote:
>> > I am a beginner so, I hope what I give, makes sense. In it's simplest
>> > form what is wrong with :-
>> >
>> > n = input("Enter a number")
>> > if n % 2 != 0 and n % 3 != 0:
>> >    print n, " Is a prime number"
>> >
>> This only gives the correct answer if n < 25. You can't test against a 
>> fixed list of divisors, there will always be a non-prime whose divisors 
>> are not in your list.
>
> Thank you for your comment which, if I understand you correctly, implies
> that prime numbers greater than 25 will not be recognised. Surely, that
> cannot be correct. However, if it is correct, could you please
> demonstrate what you mean for my education.
>

  The problem is that composite numbers over 25 will be recognised.
  11 is prime, but 55 is not.  Your program will tell me that 55 is prime. 
Similarly with 34, etc.
  A reasonably easy to understand prime number generator, that also operates 
quickly, is the classic sieve of Eratosthenes (sp).
  Google is your friend :).

  HTH,
  Glen