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

[Jose Amoreira]

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