SQL SQL素数函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15566619/
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
SQL Prime number function
提问by whytheq
If I have a number X and want to say IsPrime(X) = true/falseusing sql-server what is the best approach?
如果我有一个数字 X 并且想说IsPrime(X) = true/false使用 sql-server 什么是最好的方法？
Do I just import a table of primes or is there an algorithm that is fairly efficient for the smaller primes?
我是只导入素数表还是有一种算法对较小的素数相当有效？
Note: I'm not interested in numbers greater than approx. 10 million.
注意：我对大于约的数字不感兴趣。千万。
Ended up using the following:
最终使用了以下内容：
CREATE FUNCTION [dbo].[isPrime]
(
@number INT
)
RETURNS VARCHAR(10)
BEGIN
DECLARE @retVal VARCHAR(10) = 'TRUE';
DECLARE @x INT = 1;
DECLARE @y INT = 0;
WHILE (@x <= @number )
BEGIN
IF (( @number % @x) = 0 )
BEGIN
SET @y = @y + 1;
END
IF (@y > 2 )
BEGIN
SET @retVal = 'FALSE'
BREAK
END
SET @x = @x + 1
END
RETURN @retVal
END
采纳答案by JSuar
You could, as you said, have a table that stores all the primes up to 10 million. Then it would be trivial to look up whether a number was prime or not. The question then is which method would be faster. I suspect the table would be much faster (I have not tested this claim).
正如您所说，您可以有一张表来存储最多 1000 万个素数。那么查找一个数是否为素数就变得微不足道了。那么问题是哪种方法会更快。我怀疑桌子会快得多（我没有测试过这个说法）。
Prime Table Solution
总理表解决方案
https://www.simple-talk.com/sql/t-sql-programming/celkos-summer-sql-stumpers-prime-numbers/
Provides a few solutions and there are more in the comments.https://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/
Same here. A few solutions provided.
https://www.simple-talk.com/sql/t-sql-programming/celkos-summer-sql-stumpers-prime-numbers/
提供了一些解决方案，评论中有更多。https://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/
这里也一样。提供了一些解决方案。
SQL Function Solutions
SQL 函数解决方案
Solution 0解决方案 0Here's one solution via Finding prime numbers with a Transact-SQL function:
这是通过使用 Transact-SQL 函数查找素数的一种解决方案：
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
–- =============================================
–- Author: Nicolas Verhaeghe
–- Create date: 12/14/2008
–- Description: Determines if a given integer is a prime
/*
SELECT dbo.IsPrime(1)
SELECT dbo.IsPrime(9)
SELECT dbo.IsPrime(7867)
*/
–- =============================================
CREATE FUNCTION [dbo].[isPrime]
(
@NumberToTest int
)
RETURNS bit
AS
BEGIN
-– Declare the return variable here
DECLARE @IsPrime bit,
@Divider int
–- To speed things up, we will only attempt dividing by odd numbers
–- We first take care of all evens, except 2
IF (@NumberToTest % 2 = 0 AND @NumberToTest > 2)
SET @IsPrime = 0
ELSE
SET @IsPrime = 1 –- By default, declare the number a prime
–- We then use a loop to attempt to disprove the number is a prime
SET @Divider = 3 -– Start with the first odd superior to 1
–- We loop up through the odds until the square root of the number to test
–- or until we disprove the number is a prime
WHILE (@Divider <= floor(sqrt(@NumberToTest))) AND (@IsPrime = 1)
BEGIN
–- Simply use a modulo
IF @NumberToTest % @Divider = 0
SET @IsPrime = 0
–- We only consider odds, therefore the step is 2
SET @Divider = @Divider + 2
END
–- Return the result of the function
RETURN @IsPrime
END
Here's another solution via how to find whether is a prime or non prime with one select statement?There's more information in other comments as well.
这是通过如何使用一个 select 语句查找素数还是非素数的另一种解决方案？其他评论中也有更多信息。
CREATE FUNCTION isPrime
(
@number INT
)
RETURNS VARCHAR(10)
BEGIN
DECLARE @prime_or_notPrime INT
DECLARE @counter INT
DECLARE @retVal VARCHAR(10)
SET @retVal = 'FALSE'
SET @prime_or_notPrime = 1
SET @counter = 2
WHILE (@counter <= @number/2 )
BEGIN
IF (( @number % @counter) = 0 )
BEGIN
set @prime_or_notPrime = 0
BREAK
END
IF (@prime_or_notPrime = 1 )
BEGIN
SET @retVal = 'TRUE'
END
SET @counter = @counter + 1
END
return @retVal
END
回答by Simon UK
I suspect this hasn't occurred to many people, but all you need to check is if each new number is divisible by previous primes...
我怀疑很多人都没有发生过这种情况，但是您需要检查的是每个新数字是否可以被以前的素数整除......
create table prime (primeno bigint)
declare @counter bigint
set @counter = 2
while @counter < 1000000
begin
if not exists(select top 1 primeno from prime where @counter % primeno = 0 )
-- above, adding AND prime < @counter / 2 etc will reduce checking overheads further.
-- 上面，添加 AND prime < @counter / 2 等将进一步减少检查开销。
insert into prime select @counter
set @counter = @counter + 1
end
select * from prime order by 1
Lazy coding but even on a slow virtual pc like the one next to me you'll have everything up to a million in a few minutes. I make it 78,498 of them (if you don't count 1) unless I've overlooked something.
懒惰的编码，但即使在像我旁边这样的慢速虚拟 PC 上，您也将在几分钟内拥有多达一百万的所有内容。我做了 78,498 个（如果你不计算 1），除非我忽略了一些东西。
回答by Simon UK
CREATE proc prime
@no int
as
declare @counter int
set @counter =2
begin
while(@counter)<@no
begin
if(@no%@counter=0)
begin
select 'Not prime'
return
end
set @counter=@counter+1
end
select 'prime'
return
end
--exec prime 10
回答by Alexei
There is an interesting way to generate prime numbers without any function or iterative process (while) based on sequence generation. Basically a 2 .. @maxsequence is generated and we pick all numbers that do no have other in the sequence that current%other = 0:
有一种有趣的方法可以生成素数，无需任何函数或while基于序列生成的迭代过程 ( ) 。基本上2 .. @max会生成一个序列，我们选择所有在序列中没有其他数字的数字current%other = 0：
declare @max INT = 10000
;WITH all_numbers(n) AS
(
SELECT 2
UNION ALL
SELECT n+1 FROM all_numbers WHERE n < @max
)
select all1.n as prime
from all_numbers all1
where not exists (select 1 from all_numbers all2 where all2.n < all1.n AND all1.n % all2.n = 0)
order by all1.n
-- beware, 0 means no limit. Otherwise 32767 can be the max specified
OPTION (MAXRECURSION 0)
The main drawback of this solution is performance (e.g. it took about 17s to generate all primes until 20000), but it is more SQLish since it does not rely on explicit iterative blocks (i.e. while)
该解决方案的主要缺点是性能（例如，生成所有素数直到 20000 需要大约 17 秒），但它更 SQL，因为它不依赖于显式迭代块（即while）
回答by Farsheed
How about this (Tested on PostgreSQL):
这个怎么样（在 PostgreSQL 上测试过）：
SELECT Listagg (num, ',')
within GROUP (ORDER BY num)
FROM (SELECT n1.num num,
SUM(CASE
WHEN MOD(n1.num, n2.num) = 0 THEN 1
ELSE 0
END) AS cnt
FROM (SELECT ROWNUM num
FROM dual
CONNECT BY LEVEL <= 1000) n1,
(SELECT ROWNUM num
FROM dual
CONNECT BY LEVEL <= 1000) n2
WHERE n1.num <> 1
AND n2.num <> 1
AND n1.num >= n2.num
GROUP BY n1.num) a
WHERE cnt = 1;
回答by Daniel Marcus
Here's a simple script that works nicely. Adjust @num as needed:
这是一个运行良好的简单脚本。根据需要调整@num：
declare @nonprimes table (number int)
declare @primes table (number int)
declare @num int = 2
declare @divisor int = 1
while @num<10000
begin
while @divisor>1
begin
if @num % @divisor=0
insert @nonprimes
select @num
if @@rowcount>0 goto A
set @divisor=@divisor-1
end
insert @primes
select @num
A: set @num=@num+1
set @divisor=@num-1
end
select sum(number) from @primes
回答by user7831030
Create PROC prime @num int , @flag int OUTPUT
AS
Declare @i=50
set
while (@i<@num)
Begin
if @i%@num=0
break
set
@i=@i+1
End
if @i=@num
set
@glag=1
else
set
@flag=2
Declare @ans int
Exec prime 50,@flag=@ans OUTPUT
if @ans=1
print 'The number is prime'
else
print 'The number is composite'
