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:

http://www.4shared.com/dir/7467736/97bd7b71/sharing.html


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  6*k+1 and 6*k+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= 5*i,  k = 6*i,  p7 = 7*i
	 # p1 = (5*i-3)>>1;  p2 = (7*i-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= 5*i,  k = 6*i,  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