Print Prime Numbers with SQL query
Solution 1
In PostgreSQL probably the most fastest query that prints prime numbers up to 1000 is:
SELECT regexp_split_to_table('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,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997',E',')::int
AS x
;
It took only 16 ms on my computer.
- Note: a list of prime numbers was copied from https://en.wikipedia.org/wiki/Prime_number
and pasted into this long string
If you prefer SQL, then this works
WITH x AS (
SELECT * FROM generate_series( 2, 1000 ) x
)
SELECT x.x
FROM x
WHERE NOT EXISTS (
SELECT 1 FROM x y
WHERE x.x > y.x AND x.x % y.x = 0
)
;
It's two times slower - 31 ms.
Ans an equivalent version for Oracle:
WITH x AS(
SELECT level+1 x
FROM dual
CONNECT BY LEVEL <= 999
)
SELECT x.x
FROM x
WHERE NOT EXISTS (
SELECT 1 FROM x y
WHERE x.x > y.x AND remainder( x.x, y.x) = 0
)
;
Solution 2
The most obvious improvement is that instead of checking from 1 to n you can check from 1 to the square root of n.
A second major optimization would be to use a temporary table to store the results and check them first. This way you can iterate incrementally from 1 to n, and only check the known primes from 1 to square root of n (recursively doing that until you have a list). If you go about things this way you would probably want to set up the prime detection in a function and then do the same with your number series generator.
That second one though means extending SQL and so I don't know if that fits your requirements.
For postgresql I would use generate_series
go generate the list of numbers. I would then create functions which would then either store the list of primes in a temporary table or pass them back in and out in an ordered array and then couple them like that
Solution 3
/* Below is my solution */
/* Step 1: Get all the numbers till 1000 */
with tempa as
(
select level as Num
from dual
connect by level<=1000
),
/* Step 2: Get the Numbers for finding out the factors */
tempb as
(
select a.NUm,b.Num as Num_1
from tempa a , tempa b
where b.Num<=a.Num
),
/*Step 3:If a number has exactly 2 factors, then it is a prime number */
tempc as
(
select Num, sum(case when mod(num,num_1)=0 then 1 end) as Factor_COunt
from tempb
group by Num
)
select listagg(Num,'&') within group (order by Num)
from tempc
where Factor_COunt=2
;
Solution 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;
Solution 5
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
;
Doogle
• Techno-Functional expert with experience in best in class technologies and functional expertise in Capital Markets responsible for delivery of Compliance solutions catering to Trade surveillance requirements of Investment bank. My current engagement involves timely delivery of compliance solutions which includes data analysis, data modeling, process improvisation, requirement gathering, reporting and business intelligence. • I worked with waterfall model and lean methodology of software development involving Requirement Analysis, High Level Design, Low Level Design, Coding & deployment. • I possess excellent knowledge in Capital Markets primarily in Equities and Fixed Income space with exhaustive exposure to various regulation imposed by several regulators across globe for monitoring illegal trading in Market along with fair exposure to Anti Money Laundering and its tracking from compliance perspective. • Primary skillset includes Actimize – Best in class tool for Enterprise Trade Surveillance, AML & KYC. This includes Actimize Analytics Server and Risk Case Manager a comprehensive application for reporting, auditing, Management Insights, Dashboard, Data Masking, Data Analysis and Surveillance of illegal activities in Market Surveillance, AML space. Data Analysis and Query Optimization. • I am responsible for timely delivery of surveillance models and all enhancements. Some of the trading scenarios include Spoofing, Layering, Market Price Manipulation, Marking the Close, Parking Trades, Mifid Backtesting, Wash Trades, Off Market Trades, Front Running using Actimize for investment banks. Designed audit reports to be submitted to regulators on action taken over traders/firm involved in fraudulent activities across globe.
Updated on May 09, 2021Comments
-
Doogle almost 3 years
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.
-
Paul Spiegel almost 8 yearsYou can halve the time using only 2 and odds:
SELECT 2 x UNION ALL SELECT * FROM generate_series(3, 1000, 2) x
-
Knowledge Cube almost 7 yearsThe OP is looking for a solution which is more efficient than the code they currently have in their question. Can you explain a bit more about what exactly your code is doing and where its improvements come from?
-
Sai Ram Sagar almost 6 yearsIn SSMS we can execute the stored procedure and then execute it with the arguments required to get the required result
-
SanSolo over 5 yearsPlease use proper code formatting to make your answer readable
-
Sidrah Madiha Siddiqui about 3 yearsThis doesn't exactly solve the problem as OP wants to create this using SQL code computationally and not by hard coding in a print statement.