如果我有一个数字 X 并且想说
IsPrime(X) = true/false我是否只导入素数表，或者是否有一种对于较小素数相当有效的算法？
注意：我对大于大约的数字不感兴趣。 1000万。
最终使用以下内容：
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 万个素数。那么查找一个数是否是素数就很简单了。那么问题是哪种方法会更快。我怀疑该表会快得多（我没有测试过这个说法）。
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/
同样在这里。提供了一些解决方案。
这是通过 使用 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
这是另一种解决方案，通过 how to find if is a prime or non prime with one select statements? 其他评论中也有更多信息。
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
我怀疑很多人都没有想到这一点，但你需要检查的是每个新数字是否能被以前的素数整除......
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 etc will reduce checking overheads further.
insert into prime select @counter
set @counter = @counter + 1
end
select * from prime order by 1
懒惰编码，但即使在像我旁边的一台慢速虚拟电脑上，您也将在几分钟内获得高达一百万的所有内容。我一共做了 78,498 个（如果你不算 1），除非我忽略了一些事情。
有一种有趣的方法可以基于
序列生成来生成素数，无需任何函数或迭代过程（
while）。基本上生成了一个 2 .. @maxcurrent%other = 0declare @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/2 -- Only need to check until half numbers
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，因为它不依赖于显式迭代块（即
whileCREATE 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
这是一个运行良好的简单脚本。 根据需要调整@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
这个怎么样（在 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;
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 需要不到一秒
这是数字生成和素数检查的组合。
这是一个快速运行的素数检查器。
生成器将创建最多 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
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'