MySQL 使用 SQL 查询打印质数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37234893/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Print Prime Numbers with SQL query
提问by Doogle
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.
我是 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;
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.
我知道这个问题已经被问过多次，如果有的话，我要求更好的解决方案。更多关于它如何与 MySQL/MS SQL/PostgreSQL 一起工作的需要输入。
Any help will make my understanding better.
任何帮助都会让我更好地理解。
采纳答案by krokodilko
In PostgreSQL probably the most fastest query that prints prime numbers up to 1000 is:
在 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
;
It took only 16 ms on my computer.
在我的电脑上只用了 16 毫秒。
- Note: a list of prime numbers was copied from https://en.wikipedia.org/wiki/Prime_number
and pasted into this long string
- 注意：素数列表从https://en.wikipedia.org/wiki/Prime_number复制
并粘贴到这个长字符串中
If you prefer SQL, then this works
如果您更喜欢 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
)
;
It's two times slower - 31 ms.
它慢了两倍 - 31 毫秒。
Ans an equivalent version for Oracle:
对于 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
)
;
回答by Chris Travers
The most obvious improvement is that instead of checking from 1 to n you can check from 1 to the square root of n.
最明显的改进是，您可以从 1 到 n 的平方根，而不是从 1 到 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.
第二个主要优化是使用临时表来存储结果并首先检查它们。通过这种方式，您可以从 1 到 n 递增迭代，并且只检查从 1 到 n 的平方根的已知素数（递归地这样做，直到您有一个列表）。如果您以这种方式处理事情，您可能希望在函数中设置素数检测，然后对您的数列生成器执行相同操作。
That second one though means extending SQL and so I don't know if that fits your requirements.
第二个虽然意味着扩展 SQL，所以我不知道这是否符合您的要求。
For postgresql I would use generate_seriesgo 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
对于 postgresql，我会使用generate_seriesgo 生成数字列表。然后我会创建函数，然后将素数列表存储在临时表中，或者将它们传入和传出有序数组，然后像这样耦合它们
回答by Paul Spiegel
MariaDB (with sequence plugin)
MariaDB（带序列插件）
Similar to kordirkos algorithm:
类似于 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
);
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
MySQL
There are no sequence generating helpers in MySQL. So the sequence tables have to be created first:
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);
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;
回答by Jim West
Tested on sqlite3
在 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
在 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
回答by Андрей Черковский
Oracle and without inner select in getting part:
Oracle 并且在获取部分时没有内部选择：
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
;
回答by Rudra Ghosh
One simple one can be like this
一个简单的可以是这样的
select level id1 from dual connect by level < 2001
minus
select distinct id1 from (select level id1 from dual connect by level < 46) t1 inner join (select level id2 from dual connect by level < 11) t2
on 1=1 where t1.id1> t2.id2 and mod(id1,id2)=0 and id2<>1
回答by Ashish
Simplest method For SQL Server
SQL Server 最简单的方法
DECLARE @range int = 1000, @x INT = 2, @y INT = 2
While (@y <= @range)
BEGIN
while (@x <= @y)
begin
IF ((@y%@x) =0)
BEGIN
IF (@x = @y)
PRINT @y
break
END
IF ((@y%@x)<>0)
set @x = @x+1
end
set @x = 2
set @y = @y+1
end
回答by Sumit Kumar Sagar
MySQL QUERY SOLUTION
MySQL查询解决方案
I have solved this problem in mysql which is following:
我已经在 mysql 中解决了这个问题，如下所示：
SET @range = 1000;
SELECT GROUP_CONCAT(R2.n SEPARATOR '&')
FROM (
SELECT @ctr2:=@ctr2+1 "n"
FROM information_schema.tables R2IS1,
information_schema.tables R2IS2,
(SELECT @ctr2:=1) TI
WHERE @ctr2<@range
) R2
WHERE NOT EXISTS (
SELECT R1.n
FROM (
SELECT @ctr1:=@ctr1+1 "n"
FROM information_schema.tables R1IS1,
information_schema.tables R1IS2,
(SELECT @ctr1:=1) I1
WHERE @ctr1<@range
) R1
WHERE R2.n%R1.n=0 AND R2.n>R1.n
)
Note:No. of information_schema.tablesshould be increased for more range e.g. if range is 100000 so set the info tables by checking yourself.
注：数INFORMATION_SCHEMA.TABLES应该增加更多的范围例如，如果范围为100000所以通过检查自己设置的信息表。
回答by Maryam
This is what worked for me in the SQL server. I tried to reduce the order of my nested loops.
这就是在 SQL 服务器中对我有用的方法。我试图减少嵌套循环的顺序。
declare @var int
declare @i int
declare @result varchar (max)
set @var = 1
select @result = '2&3&5' --first few obvious prime numbers
while @var < 1000 --the first loop
begin
set @i = 3;
while @i <= @var/2 --the second loop which I attempted to reduce the order
begin
if @var%@i = 0
break;
if @i=@var/2
begin
set @result = @result + '&' + CAST(@var AS VARCHAR)
break;
end
else
set @i = @i + 1
end
set @var = @var + 1;
end
print @result
回答by sudarshan vp
/* 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
;
