11

IsPrime(X) = true/false数字が X で、 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
4

9 に答える 9

11

あなたが言ったように、最大​​ 10 million までのすべての素数を格納するテーブルを持つことができます。その場合、数値が素数かどうかを調べるのは簡単です。問題は、どの方法がより高速かということです。テーブルの方がはるかに高速になると思います (この主張はテストしていません)。

プライム テーブル ソリューション

SQL 関数ソリューション

ソリューション 0

Transact-SQL 関数を使用した素数の検索による 1 つの解決策を次に示します。

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

1つの選択ステートメントで素数か非素数かを見つける方法による別の解決策は次のとおりです。他のコメントにも詳細があります。

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
于 2013-03-22T11:51:40.907 に答える
8

これは多くの人が経験したことではないと思いますが、確認する必要があるのは、新しい数がそれぞれ前の素数で割り切れるかどうかだけです...

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 プライム < @counter / 2 などを追加すると、チェックのオーバーヘッドがさらに削減されます。

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

怠惰なコーディングですが、私の隣にあるような低速の仮想 PC でも、数分で最大 100 万のすべてを取得できます。何かを見落としていない限り、78,498 個 (1 を数えなければ) とします。

于 2015-06-30T11:41:15.827 に答える
4 
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
于 2014-04-17T12:21:32.593 に答える