tag:blogger.com,1999:blog-17155656.post114914497893604472..comments2023-04-06T12:09:13.895+02:00Comments on db4free.net blog: Filling table with prime numbersMarkus Popphttp://www.blogger.com/profile/15355530354397508921noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-17155656.post-45389233991518409852008-06-04T00:25:00.000+02:002008-06-04T00:25:00.000+02:00Oh, my bad, I forgot 1 is not prime.We could also ...Oh, my bad, I forgot 1 is not prime.<BR/><BR/>We could also filter out multiples of two, but that's left as an exercise for the reader. ;)<BR/><BR/>This version will also factor out the division, possible casting, and <BR/>floor function, replacing all that with the modulus operation (if your RDBMS does not support operator %, it probably supports function mod():<BR/><BR/><BR/>select * from artificial_range a<BR/>where a.id != 1 and not exists ( select * from artificial_range b where b.id != 1 and b.id < a.id and a.id % b.id = 0 );Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-17155656.post-78468192780333057762008-06-04T00:15:00.000+02:002008-06-04T00:15:00.000+02:00Why not just use SQL to do this:First, create a ta...Why not just use SQL to do this:<BR/><BR/><BR/>First, create a table that is just a range of numbers:<BR/><BR/>create table artificial_range (id int not null primary key auto_increment, idz int not null default 0);<BR/><BR/>insert into artificial_range(idz) values (0);<BR/><BR/>insert into artificial_range (idz) select idz from artificial_range;<BR/><BR/>Repeat the last statement, doubling the table size each time, until it reaches the length you want.<BR/><BR/>Now, assuming that your RBDMS returns a float type for integral division, just do this:<BR/><BR/>create view artifical_range_prime as <BR/>select * from artificial_range a<BR/>where not exists ( select * from artificial_range b where b.id != 1 and b.id < a.id and a.id/ b.id = floor(a.id / b.id));<BR/><BR/>Note that the predicate 'and b.id < a.id' is just to optimize the process a bit.<BR/><BR/>If your RBDMS does not return a float type for integral division, just cast one of the operand (a.id or b.id) to float prior to the divisions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-17155656.post-1149581015032009032006-06-06T10:03:00.000+02:002006-06-06T10:03:00.000+02:00Now the slow part is filling the table. That can b...Now the slow part is filling the table. That can be improved dramatically by using a doubling algorithm:<BR/><BR/>DELIMITER //<BR/>CREATE PROCEDURE fill_sieve(max INT)<BR/> DETERMINISTIC<BR/> BEGIN<BR/> DECLARE previous_max INT DEFAULT 1;<BR/><BR/> TRUNCATE sieve;<BR/><BR/> INSERT INTO sieve (id) VALUES (2);<BR/><BR/> WHILE previous_max <= max DO<BR/> INSERT INTO sieve (id) SELECT id + previous_max FROM sieve;<BR/> SET previous_max = previous_max * 2;<BR/> END WHILE;<BR/><BR/> DELETE FROM sieve WHERE id > max;<BR/><BR/> END //<BR/>DELIMITER ;<BR/><BR/>Using that method of filling brings the time to less than a second.<BR/><BR/>mysql> call sieve5(20000);<BR/>Query OK, 0 rows affected (0.63 sec)<BR/><BR/>Which can be improved further by using a memory table:<BR/><BR/>mysql> call sieve6(20000);<BR/>Query OK, 0 rows affected (0.24 sec)<BR/><BR/>-robinAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-17155656.post-1149507682381474772006-06-05T13:41:00.000+02:002006-06-05T13:41:00.000+02:00It also occurred to me that you only really need t...It also occurred to me that you only really need to loop through while the counter is < SQRT(max).<BR/><BR/>So adding that in to my previous solution:<BR/><BR/>DELIMITER //<BR/>CREATE PROCEDURE sieve3 (max INT)<BR/> DETERMINISTIC<BR/> BEGIN<BR/> DECLARE max_root INT DEFAULT CEIL(SQRT(max));<BR/> DECLARE prime INT DEFAULT 1;<BR/><BR/> CALL fill_sieve(max);<BR/><BR/> WHILE NOT ISNULL(prime) AND prime < max_root DO<BR/> SELECT MIN(id) INTO prime FROM sieve WHERE id > prime;<BR/> DELETE FROM sieve WHERE id > prime AND (id % prime) = 0;<BR/> END WHILE;<BR/><BR/> END //<BR/>DELIMITER ;<BR/><BR/>Timings:<BR/><BR/>mysql> call sieve1(20000); # original<BR/>Query OK, 0 rows affected (11.63 sec)<BR/><BR/>mysql> call sieve2(20000); # first try<BR/>Query OK, 0 rows affected (7.47 sec)<BR/><BR/>mysql> call sieve3(20000); # with sqrt<BR/>Query OK, 0 rows affected (1.62 sec)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-17155656.post-1149275781413324662006-06-02T21:16:00.000+02:002006-06-02T21:16:00.000+02:00OK, how about this? I've not bothered with improvi...OK, how about this? I've not bothered with improving the population of the sieve but I've hoicked it out into a separate procedure to tidy things up.<BR/><BR/>When 'max' is 20000, it takes about 4.27 sec to the original's 11.75 sec on my machine.<BR/><BR/> -robin<BR/><BR/>DELIMITER //<BR/><BR/>CREATE PROCEDURE fill_sieve(max INT)<BR/> DETERMINISTIC<BR/> BEGIN<BR/> DECLARE counter INT DEFAULT 2;<BR/><BR/> TRUNCATE sieve;<BR/> WHILE counter < max DO<BR/> INSERT INTO sieve (id) VALUES (counter);<BR/> SET counter = counter + 1;<BR/> END WHILE;<BR/><BR/> END //<BR/><BR/>CREATE PROCEDURE sieve (max INT)<BR/> DETERMINISTIC<BR/> BEGIN<BR/> DECLARE counter INT DEFAULT 1;<BR/><BR/> CALL fill_sieve(max);<BR/><BR/> WHILE NOT ISNULL(counter) DO<BR/> SELECT MIN(id) INTO counter FROM sieve WHERE id > counter;<BR/> DELETE FROM sieve WHERE id > counter AND (id % counter) = 0;<BR/> END WHILE;<BR/><BR/> END //<BR/><BR/>DELIMITER ;Anonymousnoreply@blogger.com