Печать простых номеров с SQL-запросом

Question

Я новичок в StackOverflow и застрял в запросе на печать простых чисел от 2 до 1000. Я использовал входной запрос ниже, если это наиболее эффективный способ его кодирования.

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; 

Я знаю, что этот вопрос задан несколько раз, и я требую лучшего решения, если оно есть. Более того, нужно вводить информацию о том, как это работает с MySQL/MS SQL/PostgreSQL.

Любая помощь поможет мне лучше понять.

Answer 1

В PostgreSQL, вероятно, самый быстрый запрос, который печатает простые числа до 1000:

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 
; 

Это заняло всего 16 мс на моем компьютере.

• Примечание: список простых чисел было скопировано с https://en.wikipedia.org/wiki/Prime_number
  и вставил в эту длинную строку

---

Если вы предпочитаете SQL, то это работает

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 
) 
; 

Это в два раза медленнее - 31 мс.

---

Ans эквивалентная версия для 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 
) 
; 

Answer 2

Наиболее очевидным улучшением является то, что вместо проверки от 1 до n вы можете проверить от 1 до квадратного корня n.

Вторая крупная оптимизация - использовать временную таблицу для хранения результатов и сначала их проверить. Таким образом, вы можете последовательно итератировать от 1 до n и проверять только известные простые числа от 1 до квадратного корня из n (рекурсивно делать это до тех пор, пока у вас нет списка). Если вы так походите, вы, вероятно, захотите настроить первичное обнаружение в функции, а затем сделать то же самое с генератором числовой серии.

Эта вторая, хотя и означает расширение SQL, и поэтому я не знаю, соответствует ли это вашим требованиям.

Для postgresql я бы использовал generate_series сгенерировал список чисел. Затем я создавал функции, которые затем либо сохраняли список простых чисел во временной таблице, либо передавали их обратно в упорядоченный массив, а затем связывали их так

Answer 3

MariaDB (с последовательностью плагин)

Аналогично kordirkos алгоритм:

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 
); 

Использование LE FT 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

Там нет последовательности генерации хелперов в MySQL. Таким образом, последовательность таблиц должны быть созданы первые:

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); 

В настоящее время подобные запросы могут быть использованы:

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 4

MySQL код:

DECLARE 
@i INT, 
@a INT, 
@count INT, 
@p nvarchar(max) 
SET @i = 1 
WHILE (@i <= 1000) 
BEGIN SET @count = 0 
SET @a = 1 
WHILE (@a <= @i) 
BEGIN IF (@i % @a = 0) SET @count = @count + 1 SET @a = @a + 1 
END IF (@count = 2) SET @P = CONCAT(@P,CONCAT(@i,'&')) SET @i = @i + 1 
END 
PRINT LEFT(@P, LEN(@P) - 1) 

Answer 5

Проверено на 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 

http://www.tutorialspoint.com/execute_sql_online.php?PID=0Bw_CjBb95KQMdlRrTXN1R2RKM1E

Проверено на 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