SQL Prime编号功能

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

Answer 1

正如你所说,你可以有一张桌子,可存储高达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

Answer 2

我怀疑很多人都没有这样做过,但你需要检查的是,每个新号码是否可以被以前的素数整除...

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

懒惰的编码,但即使在像我旁边的慢速虚拟PC上,你将在几分钟内拥有高达一百万的所有内容.除非我忽略了某些东西,否则我将其中的78,498个(如果你不算1).

Answer 3

有一种有趣的方法可以生成素数，无需任何函数或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 秒），但它更 SQL，因为它不依赖于显式迭代块（即while）