sql - SQL 素数函数

Question

如果我有一个数字 X 并且想说IsPrime(X) = true/false使用 sql-server 最好的方法是什么？

我只是导入一个素数表还是有一个算法对较小的素数相当有效？

注意：我对大于大约的数字不感兴趣。千万。

最终使用以下内容：

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

score 11 · Accepted Answer

正如你所说，你可以有一个存储所有素数的表，最高可达 1000 万。然后查找一个数字是否为素数将是微不足道的。那么问题是哪种方法会更快。我怀疑这张桌子会快得多（我没有测试过这个说法）。

Prime Table 解决方案

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 函数解决方案

解决方案 0

这是通过使用 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

解决方案 1

这是另一种解决方案，如何通过一个 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

score 8 · Accepted Answer

我怀疑很多人没有发生过这种情况，但是您需要检查的是每个新数字是否可以被先前的素数整除...

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 )

-- 上面，添加 AND prime < @counter / 2 等将进一步减少检查开销。

insert into prime select @counter
set @counter = @counter + 1
end
select * from prime order by 1

懒惰的编码，但即使在像我旁边的那台缓慢的虚拟电脑上，你也会在几分钟内拥有高达一百万的一切。除非我忽略了某些东西，否则我将其设为 78,498 个（如果您不计算 1）。

score 5 · Accepted Answer

有一种有趣的方法可以生成素数，而无需任何函数或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)

该解决方案的主要缺点是性能（例如，在 20000 之前生成所有素数大约需要 17 秒），但它更 SQLish，因为它不依赖于显式迭代块（即while）

score 4 · Accepted Answer

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

score 1 · Accepted Answer

这个怎么样（在 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;

score 1 · Accepted Answer

declare @max INT = 50000
declare @all_numbers table (n int not null primary key, squareRoot decimal(10,1))
;WITH all_odds(n) AS
(
    SELECT 3
    UNION ALL
    SELECT n+2 FROM all_odds WHERE n+2 < @max
)
    INSERT INTO @all_numbers
    SELECT 2 as n, SQRT(2)
    UNION ALL
    SELECT n, SQRT(n) FROM all_odds
    OPTION (MAXRECURSION 0)

select all1.n as prime
from @all_numbers all1
where not exists (select 1 from @all_numbers all2 where all2.n <= all1.squareRoot AND all1.n % all2.n = 0)
order by all1.n

这需要不到一秒的时间 50k

score 1 · Accepted Answer

这是数字生成和检查素数的组合。

这是一个快速运行的素数检查器。

生成器将创建最多 10,000 个数字的列表。
@CheckNumber 可以设置为任何需要的值。

随意扩大最大生成数量以满足您的需求。

DECLARE @CheckNumber INT;
SET @CheckNumber = 29;

with data as (
    SELECT (ones.n + 10*tens.n + 100*hundreds.n + 1000*thousands.n ) + 1 as number
FROM (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) ones(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) tens(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) hundreds(n),
     (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) thousands(n)
)

select sub1.number1
from (
  select distinct d1.number as number1, d2.number as number2
  from data as d1 
  cross join data as d2
  where d1.number % d2.number != 0
) as sub1
group by sub1.number1
having count(sub1.number2) = max(sub1.number2)-2
and sub1.number1 = @CheckNumber
order by sub1.number1

score 0 · Accepted Answer

这是一个运行良好的简单脚本。根据需要调整@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

score -3 · Accepted Answer

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'

sql - SQL 素数函数

9 回答 9

Prime Table 解决方案

SQL 函数解决方案

Related

Reference