Print Prime Numbers with SQL query

Question

I am new to StackOverflow and have got stuck with a query to print prime numbers from 2 to 1000. I have used the below query need input if this is the most efficient way to code it.

WITH NUM AS (
    SELECT LEVEL N 
    FROM DUAL CONNECT BY LEVEL <= 1000
) 
SELECT LISTAGG(B.N,'-') WITHIN GROUP(ORDER BY B.N) AS PRIMES 
FROM (
    SELECT  N,
            CASE WHEN EXISTS (
                                SELECT NULL 
                                FROM NUM N_INNER 
                                WHERE N_INNER .N > 1 
                                AND N_INNER.N < NUM.N 
                                AND MOD(NUM.N, N_INNER.N)=0
                            ) THEN 
                'NO PRIME' 
            ELSE 
                'PRIME' 
            END IS_PRIME 
        FROM NUM
    ) B 
WHERE B.IS_PRIME='PRIME' 
AND B.N!=1;

I know this question has been asked multiple times and I am requesting better solution if any. More over need input on how this works with MySQL/MS SQL/PostgreSQL.

Any help will make my understanding better.

Answer 1

Simple query in PostgreSQL:

SELECT serA.el AS prime
FROM generate_series(2, 100) serA(el)
LEFT JOIN generate_series(2, 100) serB(el) ON serA.el >= POWER(serB.el, 2)
                                              AND serA.el % serB.el = 0
WHERE serB.el IS NULL

Enjoy! :)

Answer 2

Tested on sqlite3

WITH nums(n) AS 
(
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 100
)

SELECT n 
FROM (
  SELECT n FROM nums
) 
WHERE n NOT IN (
  SELECT n
  FROM nums 
  JOIN ( SELECT n AS n2 FROM nums )
  WHERE n  <> 1 
    AND n2 <> 1 
    AND n  <> n2 
    AND n2 <  n 
    AND n % n2 = 0
  ORDER BY n
)
AND n <> 1

Tested on Vertica 8

WITH seq AS (
  SELECT ROW_NUMBER() OVER() AS n 
  FROM (
      SELECT 1 
      FROM (
          SELECT date(0) + INTERVAL '1 second' AS i 
          UNION ALL
          SELECT date(0) + INTERVAL '100 seconds' AS i 
      ) _
      TIMESERIES tm AS '1 second' OVER(ORDER BY i)
  ) _
)
SELECT n 
FROM (SELECT n FROM seq) _  
WHERE n NOT IN (
  SELECT n FROM (
    SELECT s1.n AS n, s2.n AS n2
    FROM seq AS s1 
    CROSS JOIN seq AS s2
    ORDER BY n, n2
  ) _
  WHERE n  <> 1 
    AND n2 <> 1 
    AND n  <> n2 
    AND n2 <  n 
    AND n % n2 = 0
)
AND n <> 1
ORDER BY n

Answer 3

For SQL Server We can use below CTE 

SET NOCOUNT ON

;WITH Prim AS
(
    SELECT 2 AS Value 
    UNION ALL
    SELECT t.Value+1 AS VAlue 
    FROM Prim t
    WHERE t.Value < 1000
)SELECT * 
FROM Prim t
WHERE NOT EXISTS(   SELECT 1 FROM prim t2
                WHERE t.Value % t2.Value = 0 
                AND t.Value != t2. Value)
OPTION (MAXRECURSION 0)

Answer 4

MariaDB (with sequence plugin)

Similar to kordirkos algorithm:

select 2 as p union all
select n.seq
from seq_3_to_1000_step_2 n
where not exists (
    select 1
    from seq_3_to_32_step_2 q
    where q.seq < n.seq
      and n.seq mod q.seq = 0
);

Using LEFT JOIN:

select 2 as p union all
select n.seq
from seq_3_to_1000_step_2 n
left join seq_3_to_32_step_2 q
      on  q.seq < n.seq
      and n.seq mod q.seq = 0
where q.seq is null;

MySQL

There are no sequence generating helpers in MySQL. So the sequence tables have to be created first:

drop temporary table if exists n;
create temporary table if not exists n engine=memory
    select t2.c*100 + t1.c*10 + t0.c + 1 as seq from 
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t0,
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t1,
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t2
    having seq > 2 and seq % 2 != 0;

drop temporary table if exists q;
create temporary table if not exists q engine=memory
    select *
    from n
    where seq <= 32;
alter table q add primary key seq (seq);

Now similar queries can be used:

select 2 as p union all
select n.seq
from n
where not exists (
    select 1
    from q
    where q.seq < n.seq
      and n.seq mod q.seq = 0
);

select 2 as p union all
select n.seq
from n
left join q
    on  q.seq < n.seq
    and n.seq mod q.seq = 0
where q.seq is null;

sqlfiddle

Answer 5

The below code works to find prime numbers in SQL

Tested on SampleDB of local server

CREATE procedure sp_PrimeNumber(@number int)
as 
begin
declare @i int
declare @j int
declare @isPrime int
set @isPrime=1
set @i=2
set @j=2
while(@i<=@number)
begin
    while(@j<=@number)
    begin
        if((@i<>@j) and (@i%@j=0))
        begin
            set @isPrime=0
            break
        end
        else
        begin
            set @j=@j+1
        end
    end
    if(@isPrime=1)
    begin
        SELECT @i
    end
    set @isPrime=1
    set @i=@i+1
    set @j=2
end
end

I have created the stored procedure which has a parameter @number to find the prime numbers up to that given number

In order to get the prime numbers we can execute the below stored procedure

EXECUTE sp_PrimeNumber 100  -- gives prime numbers up to 100

If you are new to stored procedures and want to find the prime numbers in SQL we can use the below code

Tested on master DB

declare @i int
declare @j int
declare @isPrime int
set @isPrime=1
set @i=2
set @j=2
while(@i<=100)
begin
    while(@j<=100)
    begin
        if((@i<>@j) and (@i%@j=0))
        begin
            set @isPrime=0
            break
        end
        else
        begin
            set @j=@j+1
        end
    end
    if(@isPrime=1)
    begin
        SELECT @i
    end
    set @isPrime=1
    set @i=@i+1
    set @j=2
end

This code can give the prime numbers between 1 to 100. If we want to find more prime numbers edit the @i and @j arguments in the while loop and execute

Answer 6

Oracle and without inner select in getting part:

 with tmp(id)
as (
    select level  id from dual connect by level <= 100 
) select t1.id from tmp t1
 JOIN tmp t2
 on MOD(t1.id, t2.id) = 0
 group by t1.ID
 having count(t1.id) = 2
 order by t1.ID
 ;