Sieve of Eratosthenes

In the previous step we created a simple stored procedure that generated prime numbers and saved them in a table of a database. Well it doesn't actually generate primes but it uses the Sieve of Eratosthenes to separate the primes from the composites.

We will optimize this stored procedure by first making sure we do not sieve what has already been sieved. Suppose we are looking to delete numbers that can be divided by n; any surviving number in our table would be one that cannot be divided by (n-1) which implies that the first composite will be n^2

The second optimization is to skip over the numbers that are already in the table from previous sieving attempts. Combining these optimizations together yields the following code:


    DECLARE sqrt_p INT;
    DECLARE i INT;
    DECLARE minp INT;

    SELECT IFNULL(MAX(value),1) INTO minp FROM primeNumbers;
    
    IF P > minp THEN
        # don't bother, we already have this in the table.
        SET sqrt_p = CEIL(SQRT(P));
        
        IF minp < 2 THEN
            # starting from an empty table
            INSERT INTO primeNumbers(value) VALUES(2);
            SET i=3;
        ELSE
            IF (i%2 = 0) THEN
                SET i = minp+1;
            ELSE
                SET i = minp+2;
            END IF;
        END IF;            

        WHILE i <= P DO
            # populate table with all odd numbers. Later we delete non primes.
            INSERT INTO primeNumbers(value) VALUES(i);
            SET i = i+2;
        END WHILE;

        SET i=3;

        # now composite numbers greater than minp will be deleted.
        WHILE i < sqrt_p DO
            IF (minp < (i*i -1)) THEN
                # we don't want to sieve what has already been sieved
                SET minp = i*i -1;
            END IF;           
            DELETE FROM primeNumbers WHERE value > minp AND (value%i)=0;
            SET i = i+2;
        END WHILE;
    END IF;

We are still dividing by all the integers but the reality is that with the Sieve of Eratosthenes you only need to use the known primes as the divisors.

    WHILE i < sqrt_p DO
        IF (minp < (i*i -1)) THEN
            # we don't want to sieve what has already been sieved
            SET minp = i*i -1;
        END IF;

        # are we dividing by a prime?
        SELECT IFNULL(value,0) INTO itest FROM primeNumbers WHERE value=i;
        IF itest > 0 THEN
            DELETE FROM primeNumbers WHERE value > minp AND (value%i)=0;
        END IF;
        SET i = i+2;
    END WHILE;

We can try to improve this code a bit more but that would be nitpicking. On my ancient server it finds all the primes under 1,000,000 in less than 3 minutes. But can it be faster? Well there is another algorithm that's a bit faster. We will have a look into that later.