Search code examples
mysqlprimes

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.


Solution

  • 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.