Sieve of Eratosthenes

More Articles

Strange Characters and Blobs

perl File upload progress bar.

LPI Certification

Opinions are devided as to whether it's better to keep a list of prime numbers on disk or to generate them as needed. I do not have my own opinion on the subject but if you need to keep a list of primes on permanent storage here is a MySQL stored procedure to generate them and insert them into a table.

The numbers are generated using the well known Sieve of Eratosthenes and stored into a very simple one column table.

        CREATE PROCEDURE sp_findPrimes(P INT)
            DECLARE sqrt_p INT;
            DECLARE i INT;
            SET sqrt_p = CEIL(SQRT(P));
            INSERT INTO primeNumbers(value) VALUES(2);
            SET i=3;
            WHILE i <= P DO
                INSERT INTO primeNumbers(value) VALUES(i);
                SET i = i+2;
            END WHILE;

            SET i=2;
            WHILE i < sqrt_p DO
                DELETE FROM primeNumbers WHERE value > i AND (value%i)=0;
                SET i = i+1;
            END WHILE;  
        DELIMITER ;    

Obviously this isn't a highly optimized bit of code or a very accurate implementation of the algorithm. But it has the basic elements; That of generating a list of numbers and gradually removing from it. If any number in the list is divisable by another, it's not a prime and it's deleted. The function is reasonably fast but doesn't scale all that well.

mysql> CALL find_primes(10000);
Query OK, 0 rows affected (0.55 sec)

mysql> CALL find_primes(100000);
Query OK, 0 rows affected (9.25 sec)

mysql> CALL find_primes(1000000);
Query OK, 0 rows affected (4 min 55.47 sec)

In the next step we will try to optimize this stored procedure

Copyright © Raditha Dissanayake 2013