[Tutor] prime numbers

[Timothy M. Brauch]

>Hello folks
>I am wanting to do an exercise that calls for a function to calculate prime
>numbers. I know that primes can *only* be divided by themself or by 1, and
>nothing else. My difficulty is translating this into parsimonious code
>without labouriously working out all the possible prime numbers as
conditions
>for the if control.
>So far I have attempted % and /, and various combinations, but after a
while I
>am almost including all the primes anyway. Can someone give me a nudge in
the
>right direction please.
>Much appreciated
>AmF

I can think of one way to write short code to check if a number is prime.
The smallest factor of a pair of factors must be less than or equal to the
square root of the number.  I can't think of a clear way to say that.  Maybe
a few examples...

4 --> (1,4) (2,2).  2 <= sqrt(4)
6 --> (1,6) (2,3).  2 <= sqrt(6)
8 --> (1,8) (2,4).  2 <= sqrt(8)
16 --> (1,16) (2,8) (4,4).  4 <= sqrt(16)
24 --> (1,24) (2,12) (3,8) (4,6) 4<= sqrt(24)

A few more examples should be pretty convincing it is true.  If requested, I
could write up some sort of rigorous proof this is the case, but I am tired
after doing proofs all day long.  So, the short coding way to find if a
number was prime or not would be to simply check it against all integers
that are less than the square root of the number.

However, just a little warning, this would only take a few lines of code,
but it will be painfully slow as your numbers get bigger.  If you are just
sticking with numbers say less than 100**2, then it probably won't take too
long to check 100 divisions.  Just remember, though, this code is far from
efficient.  I guess you could write it so once it found one factor, to stop;
that should increase the efficiency, but it would also add a few lines to
the code.

 - Tim