MAK MAK - 3 months ago 20
MySQL Question

sql query for finding prime numbers

Suppose I have numbers from 1 to 100 in a table.
I need to write a query to extract all the prime numbers from this table. how can I achieve this with a very basic and simple query without using any sort of procedures or loops.

Answer

MyISAM was chosen for a reason. I will explain in comments. Mainly to guarantee a no innodb gap anomoly during self-inserts (thus throwing off the id's). Don't look into the schema part of it too much. I just needed to generate a table 1 to 100.

As for MyISAM, it does not suffer from the INNODB gap anomoly ref1 ref2 and it guaranteed no gaps from 1 to 100 that can occur during self-inserts and INNODB gap ranges.

Anyway, had you provided the actual table I would not need to mention that. Or an ALTER TABLE can change the engine after the data load.

Schema

create table nums
(   id int auto_increment primary key,
    thing char(1) null
)ENGINE=MyISAM;

insert nums(thing) values(null),(null),(null),(null),(null),(null),(null);
insert nums(thing) select thing from nums;
insert nums(thing) select thing from nums;
insert nums(thing) select thing from nums;
insert nums(thing) select thing from nums;
select count(*) from nums; -- 112
delete from nums where id>100;
select min(id),max(id),count(*) from nums;
-- 1 100 100

Query

select id from nums where id>1 and id not in 
(   select distinct n2id 
    from 
    (   select n1.id as n1id, n2.id as n2id 
        from nums n1 
        cross join nums n2 
        where n1.id<(n2.id) and n1.id>1 and (n2.id MOD n1.id = 0) 
    ) xDerived 
) 
order by id; 

Results

+----+
| id |
+----+
|  2 |
|  3 |
|  5 |
|  7 |
| 11 |
| 13 |
| 17 |
| 19 |
| 23 |
| 29 |
| 31 |
| 37 |
| 41 |
| 43 |
| 47 |
| 53 |
| 59 |
| 61 |
| 67 |
| 71 |
| 73 |
| 79 |
| 83 |
| 89 |
| 97 |
+----+
25 rows in set (0.00 sec)

Note, ref2 above is an exaggerated "quickly create a 4.7M row table" that would have definitely create INNODB id gaps if not done that way. It is just a known fact with that engine.