Sieve of Eratosthenes
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) BEGIN 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; END // 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