## Friday, August 11, 2006

### Use The Sieve of Eratosthenes To Find All PrimeNumbers Below 1 Million

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It was created by Eratosthenes, an ancient Greek mathematician. Wheel factorization is often applied on the list of integers to be checked for primality, before Sieve of Eratosthenes is used, to increase the speed.

Algorithm
Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)
Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)
Strike off 2 and all multiples of 2 from List A.
The first remaining number in the list is a prime number. Write this number into List B.
Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
Repeat steps 4 through 6 until no more numbers are left in List A.

`SET NOCOUNT ONDECLARE @i INT-- Create a 10-digit tableDECLARE @D TABLE (N INT)INSERT INTO @D (N) SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4INSERT INTO @D (N) SELECT N+5 FROM @D-- build a small sieve table between 2 and 1000DECLARE @T TABLE (N INT)INSERT INTO @T( N )SELECT 1+A.N+10*(B.N+10*C.N)FROM @D A, @D B, @D CDELETE FROM @T WHERE N = 1SET @I = 2WHILE @I <= SQRT(1000)BEGIN    DELETE FROM @T WHERE N % @I = 0 AND N > @I    SET @I = @I + 1END-- Create large table between 1001 and 1000000SELECT A+10*(B+10*(C+10*(D+10*(E+ 10*F)))) AS NINTO #PFROM(    SELECT A.N AS A, B.N AS B, C.N AS C, D.N AS D, E.N AS E, F.N AS F    FROM @D A, @D B, @D C, @D D, @D E, @D F    WHERE A.N in (1, 3, 7, 9)  -- Not divisible by 2 or 5) blahWHERE (A+B+C+D+E+F) % 3 <> 0 -- Or 3    AND (A+3*B+2*C-D-3*E-2*F) % 7 <> 0 -- Or 7    AND (B-A+D-C+F-E) % 11 <> 0 -- Or 11    AND D|E|F <> 0 -- Don't include the first 1000 numbers, --we already have these in the small sieve tableUNION ALL SELECT 1000000-- sieve the big table with smaller oneSELECT @I = 2 WHILE @I IS NOT NULLBEGIN    DELETE FROM #P WHERE N% @I = 0    SELECT @I = MIN(N) FROM @T WHERE N > @IEND-- add primes up to 1000INSERT INTO #P SELECT N FROM @T-- Here are the results--78498 rowsSELECT  * FROM #P ORDER BY 1drop table #Pgo`