Just goofing around--not making any claims about efficiency other
than this is the shortest way I've found to do this over my years
of working with different flavors of SQL. This one is running
with MySQL 4.1.
Has anyone done better?
--jim
How it works:
1. a MySQL variable (@num) is used to track the number being
tested for primality
2. a table is kept of the odd prime numbers and the respective
modulos of @num
3. each iteration:
a. @num is increased by 2 (only checking odd numbers)
b. each of the modulos are UPDATEd by increasing by 2
c. if any of the modulos are >= their respective primes,
they're decreased by that amount
d. if any of the resulting modulos = 0,
then the number is composite,
else the number is prime and is added to the modulos
table
Efficiency is O(n**2), but it should perform better in the long
run than a sieve both in terms of speed and storage.
in MySQL:
/* First-Time Setup: */
DROP TABLE IF EXISTS modulos;
CREATE TABLE modulos (
prime INT UNSIGNED NOT NULL,
modulo INT UNSIGNED NOT NULL
);
INSERT INTO modulos VALUES (3,0);
SELECT @num := 3;
/* repeat these four lines until max(prime) > maxint */
SELECT @num := @num+2;
UPDATE modulos SET modulo = modulo+2;
UPDATE modulos SET modulo = modulo-prime WHERE modulo >= prime;
INSERT INTO modulos (prime,modulo) SELECT @num,0 FROM modulos WHERE 0 NOT IN (SELECT
modulo FROM
modulos) LIMIT 1;
same thing in PHP:
<?PHP
set_time_limit(0);
mysql_connect('localhost','user','pass');
mysql_select_db('pfind');
mysql_query('DROP TABLE IF EXISTS modulos');
mysql_query('CREATE TABLE modulos (
prime INT UNSIGNED NOT NULL,
modulo INT UNSIGNED NOT NULL
)');
mysql_query('INSERT INTO modulos VALUES (3,0)');
mysql_query('SELECT @num := 3');
for ($i=0;$i<1000000;$i++)
{
mysql_query('SELECT @num := @num+2');
mysql_query('UPDATE modulos SET modulo = modulo+2');
mysql_query('UPDATE modulos SET modulo = modulo-prime WHERE modulo >= prime');
mysql_query('INSERT INTO modulos (prime,modulo) SELECT @num,0 FROM modulos WHERE 0
NOT IN
(SELECT modulo FROM modulos) LIMIT 1;');
if (mysql_affected_rows())
{
print (2*$i+5)."\n";
}
}
$row = mysql_fetch_row(mysql_query('select max(prime) from modulos'));
print $row[0]."\n";
?>
--
MySQL General Mailing List
For list archives: http://lists.mysql.com/mysql
To unsubscribe: http://lists.mysql.com/[EMAIL PROTECTED]
