SQL素数函数

本文介绍了SQL素数函数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

If I have a number X and want to say IsPrime(X) = true/false using sql-server what is the best approach?

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

Do I just import a table of primes or is there an algorithm that is fairly efficient for the smaller primes?

注意:我对大于约的数字不感兴趣.1000 万.

Note: I'm not interested in numbers greater than approx. 10 million.

最终使用了以下内容:

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

推荐答案

你可以，如你所说，有一个 存储最多 1000 万个质数.那么查找一个数是否为素数就变得微不足道了.那么问题是哪种方法会更快.我怀疑这个表会快得多(我没有测试过这个说法).

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).

• www.simple-talk/sql/t-sql-programming/celkos-summer-sql-stumpers-prime-numbers/ 提供了一些解决方案，还有更多评论.

• www.simple-talk/sql/t-sql-programming/celkos-summer-sql-stumpers-prime-numbers/ Provides a few solutions and there are more in the comments.

sqlserverfast/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/同样在这里.提供了一些解决方案.

sqlserverfast/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/ Same here. A few solutions provided.

这是通过 使用 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 语句确定是素数还是非素数? 其他评论中也有更多信息.

Solution 1

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.

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