[Tutor] [Edu-sig] collection of ACM programming problems (fwd)
Fri, 12 Jan 2001 10:33:25 +0000
Joel Ricker wrote:
> ... 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.
> 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...