From: jzakiya <jzakiya@...>
Date: 2008-06-08T13:28:49+09:00
Subject: Re: Ultimate Prime Sieve -- Sieve of Zakiya (SoZ)

On Jun 7, 10:58 pm, jzakiya <jzak...@mail.com> wrote:
> 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

The Ruby code from the paper can be seen here;

http://snippets.dzone.com/posts/show/5610