7 - 11........i didn't even look at this.............believe it or not.......
'
For example, to find all the odd primes less than or equal to 100 we first list the odd numbers from 3 to 100 (why even list the evens?) The first number is 3 so it is the first odd prime--cross out all of its multiples. Now the first number left is 5, the second odd prime--cross out all of its multiples. Repeat with 7 and then since the first number left, 11, is larger than the square root of 100, all of the numbers left are primes.
This method is so fast that there is no reason to store a large list of primes on a computer--an efficient implementation can find them faster than a computer can read from a disk.
Bressoud has a pseudocode implementation of this algorithm [Bressoud89, p19] and Riesel a PASCAL implementation [Riesel94, p6]. It is also possible to create an even faster sieve based on quadratic forms.
No comments:
Post a Comment