I provided a fairly simple imple
Now you can revise the fn_isprime
function to use the highest primorial
that you have in the primorials table. Note that this implementation
assumes that the coprimes table contains all coprimes of the
primorial, and that the primes table contains all primes smaller than the
primorial:
-- function fn_isprime, version 4
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
-- check if @n
is an obvious prime or nonprime
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;
-- check if
primes table is sufficient to test primality of @n
declare
@sqrt
as bigint,
@maxp
as bigint;
set @sqrt = cast(sqrt(@n) as bigint);
set @maxp = (select max(p) from dbo.primes);
if @n <= @maxp
return case when exists(
select * from dbo.primes where p = @n) then 1 else 0 end;
if @sqrt <= @maxp
return case when exists(
select * from dbo.primes
where p >= @explicitprime and
p <= @sqrt and
@n%p = 0)
then 0 else 1 end;
-- if primes
table is not sufficient to test primality of @n
-- use
primorial-coprimes test
declare
@from
as bigint,
@to
as bigint,
@min
as bigint,
@max
as bigint,
@c#
as bigint; -- primorial
set @from = @explicitprime;
if @maxp + 2 >
@explicitprime set @from = @maxp + 2;
set @to = @sqrt;
set @c# = (select max(primorial) from dbo.primorials);
-- 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
-- check if @n exists in primes
when exists(select * from dbo.primes where p = @n) then 1
-- check if any prime in primes table divides @n
-- important: assuming primes table contains at least
-- all primes that are smaller than @c#
when exists(
select * from dbo.primes
where p
>= @explicitprime and
p <= @sqrt and
@n%p = 0)
then
0
-- handle divisors before @min k
when exists(
select * from(
select
@c#*(@min-1)+coprime as m
from
dbo.coprimes
where
primorial = @c#
and
coprime >= @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+coprime as
m
from
dbo.fn_nums(@min, @max) as k
cross
join dbo.coprimes
where
primorial = @c#) as
divisors
where
@n%m = 0) then 0
-- handle divisors after @max k
when exists(
select * from(
select
@c#*(@max+1)+coprime as m
from
dbo.coprimes
where
primorial = @c#
and
coprime <= @to -
@c#*(@max+1)) as divisors
where
@n%m = 0) then 0
else 1
end;
end;
go
Version 4 of the fn_isprime
function had the following run times to test
the primality of the following primes:
10,000,000,000,037: < 1 sec
100,000,000,000,031: < 1 sec
1,000,000,000,000,037: 6 sec
10,000,000,000,000,061: 24 sec
100,000,000,000,000,003: 78 sec
1,000,000,000,000,000,003: 257 sec
Prev. page
1
2
3
4
[5]
6
7
next page 
