This is to announce the release of my paper “Ultimate Prime Sieve –
Sieve of Zakiiya (SoZ)” in which I show and explain the development of
a class of Number Theory Sieves to generate prime numbers. I also use
the number theory to then create the fastest, and deterministic,
primality tester. I used Ruby 1.9.0-1 as my development environment
on a P4 2.8 Ghz laptop.
You can get the pdf of my paper from here:
Below is a sample of one of the prime generators, and the primality
tester.
class Integer
def primesP3a
# all prime candidates > 3 are of form 6k+1 and 6k+5
# initialize sieve array with only these candidate values
# where sieve contains the odd integers representatives
# convert integers to array indices/vals by i = (n-3)>>1 =
(n>>1)-1
n1, n2 = -1, 1; lndx= (self-1) >>1; sieve = []
while n2 < lndx
n1 +=3; n2 += 3; sieve[n1] = n1; sieve[n2] = n2
end
#now initialize sieve array with (odd) primes < 6, resize array
sieve[0] =0; sieve[1]=1; sieve=sieve[0…lndx-1]
5.step(Math.sqrt(self).to_i, 2) do |i|
next unless sieve[(i>>1) - 1]
p5= 5i, k = 6i, p7 = 7*i
p1 = (5i-3)>>1; p2 = (7i-3)>>1; k = (6*i)>>1
i6 = 6*i; p1 = (i6-i-3)>>1; p2 = (i6+i-3)>>1; k = i6>>1
while p1 < lndx
sieve[p1] = nil; sieve[p2] = nil; p1 += k; p2 += k
end
end
return [2] if self < 3
[2]+([nil]+sieve).compact!.map {|i| (i<<1) +3 }
end
def primz?
# number theory based deterministic primality tester
n = self.abs
return true if [2, 3, 5].include? n
return false if n == 1 || n & 1 == 0
return false if n > 5 && ( ! [1, 5].include?(n%6) || n%5 == 0)
7.step(Math.sqrt(n).to_i,2) do |i|
p5= 5i, k = 6i, p7 = 7*i
p1 = 5*i; k = p1+i; p2 = k+i
return false if [(n-p1)%k , (n-p2)%k].include? 0
end
return true
end
end
Now to generate an array of the primes up to some N just do:
1000001.primesP3a
To check the primality of any integer just do: 13328237.primz?
The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love
to see the various prime generators benchmarked with other
interpretors. I would also like to see at least the primality tester
make it into the standard library, since its so short, elegant, and
good.
Have fun with the code.
Jabari Zakiya