-- function fn_isprime
-- function fn_isprime, version 2
if object_id('dbo.fn_isprime') is not null
drop function dbo.fn_isprime;
go
create function
dbo.fn_isprime(@n
as bigint) returns bit
with returns null on null input
as
begin
declare
@explicitprime as bigint;
set
@explicitprime = 23;
if @n < @explicitprime
if @n in (2, 3, 5, 7, 11, 13, 17, 19) return 1 else return 0;
if @n%2 = 0 or @n%3 = 0 or @n%5 = 0 or @n%7 = 0
or @n%11 = 0 or @n%13 = 0 or @n%17 = 0 or @n%19 = 0 return 0;
if @n < cast(square(@explicitprime) as bigint) return 1;
declare
@sqrt as bigint,
@from as bigint,
@to
as bigint,
@min
as bigint,
@max
as bigint;
set @sqrt = cast(sqrt(@n) as bigint);
set @from = @explicitprime;
set @to = @sqrt;
set @min = @from / 2;
set @max = (@to-1) / 2;
return
case when exists
(select * from dbo.fn_nums(@min, @max) where @n%(n*2+1) = 0)
then 0 else 1 end
end;
go
This implementation produces about half the number of
divisors
compared to the previous implementation. But you can optimize it even
further. Every prime can be expressed as the expression c#k+i,
where
c# is a primorial (product of all primes up to the prime number c), k is
an integer, and i is a coprime of c# smaller than c#
(two integers are
said to be coprime if they don’t share any common divisor
besides 1;
in other words, c# and i are coprime if
their greatest common divisor is
1). So, to check whether @n is a prime, you will
need to check
whether any prime smaller than c# and smaller than floor(sqrt(@n))
divides @n, and if none divides @n, check whether
any m > c# and <=
floor(sqrt(@n)) divides @n, where
m = c#k+i.
For example, say you choose the primorial 3# (2*3=6). The
coprimes
of 6 that are smaller than 6 are 1 and 5. If @n is
equal to 10001, floor
(sqrt(@n)) is 100. So first, you need to check
if any prime smaller than
6 (2, 3 and 5) divides 10001. Since none of these primes divides
10001, you need to check whether any m = c#k+i in the
range > 6 and
<= 100 divides @n. Within this range you will find the following m
values: 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55,
59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97.
This approach
reduces the number of divisors you need to produce and check. Here’s
an example for the function implementation based on this approach
using the primorial 6 (inline comments describe the technicalities):
-- function fn_isprime, version 3
if object_id('dbo.fn_isprime') is not null
drop function dbo.fn_isprime;
go
create function
dbo.fn_isprime(@n
as bigint) returns bit
with returns null on null input
as
begin
declare
@explicitprime as
bigint;
set
@explicitprime = 23;
if @n < @explicitprime
if
@n in (2, 3, 5, 7, 11, 13, 17, 19) return 1 else return 0;
if @n%2 = 0 or @n%3 = 0 or @n%5 = 0 or @n%7 = 0
or @n%11 = 0 or @n%13 = 0 or @n%17 = 0 or @n%19 = 0 return 0;
if @n < cast(square(@explicitprime) as bigint) return 1;
declare
@sqrt
as bigint,
@from
as bigint,
@to
as bigint,
@min
as bigint,
@max
as bigint,
@c#
as bigint; -- primorial
set @sqrt = cast(sqrt(@n) as bigint);
set @from = @explicitprime;
set @to = @sqrt;
set @c# = 6;
-- Formula for
divisors that are potential primes: m = c#k+i
-- m - divisor,
c# - primorial, k - integer, i - coprime to c#
-- Set @min and
@max k,
-- such that k
represents complete primorial-sized segments
-- of divisors
within the range @from - @to.
-- The partial
segments of divisors for k = @min - 1 and @max + 1
-- will be
handled separately.
set @min = (@from-1)/@c# + 1;
set @max = (@to -1)/@c# - 1;
return
case
-- handle divisors before @min k
when exists(
select * from(
select
@c#*(@min-1)+i as m
from (select 1 as i union all select 5) as coprimes
where
i >= @from -
@c#*(@min-1)) as divisors
where
@n%m = 0) then 0
-- handle divisors in the range @min - @max k
when exists(
select * from(
select
@c#*n+i as m
from
dbo.fn_nums(@min, @max) as k
cross
join (select 1 as i union all select 5)
as
coprimes) as
divisors
where
@n%m = 0) then 0
-- handle divisors after @max k
when exists(
select * from(
select
@c#*(@max+1)+i as m
from (select 1 as i union all select 5) as coprimes
where
i <= @to -
@c#*(@max+1)) as divisors
where
@n%m = 0) then 0
else 1
end;
end;
go
Prev. page
1
[2]
3
4
5
6
7
next page 
