# [Tutor] [Edu-sig] collection of ACM programming problems (fwd)

**Jose Amoreira
**
amoreira@mercury.ubi.pt

*Fri, 12 Jan 2001 10:33:25 +0000*

Joel Ricker wrote:
[...snip...]
>* ... I assume you took the
*>* normal route of testing each number against an increasing number until
*>* either it divides evenly or gets larger than half the tested number.
*
Sorry to drop in, but I thought that you just have to go up to the *square
root* (instead of half) of the tested number. This is not a formal
demonstration, but if the tested number devides evenly by its half, it also
devides evenly by 2, wich comes first in this increasing series of devides.
>* Well
*>* try doing a routine that finds a list of prime numbers, say 1 to 1000 using
*>* multiplication instead. Its faster and actually increases speed as it tests
*>* (ie, the number of calculations to test to see if 500 is prime is fewer than
*>* the number of tests to see if 250 is prime).
*
I guess that the sieve of erastothenes is a partial candidate for your request;
it is, at least, a multiplications only algorithm. It goes as this:
1 take a list of all integers from one to (say) n=1000;
2 remove all mutiples of k=2;
3 take the first element bigger than k not yet removed (the 1st time this
step is done, that's 3) and remove all its multiples;
4 repeat step 3 while k is smaller the sqrt(n)
What's left in the list after this procedure are all the primes up to n.
Just my 2c...
Cheers
Ze