Sieve of Eratosthenes

More Articles

Strange Characters and Blobs

perl File upload progress bar.

LPI Certification

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  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  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.

See also: PHP version