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 You can see/download the code from the paper here: http://snippets.dzone.com/posts/show/5610 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? For GIMPS, the deterministic primality tester alone should be worth its weight in gold. It should facilitate testing of primes on the order for GIMPS with simple accomodations for big-numbers, since all you have to do is a sqrt, some modulo operations, and subtractions. Please implement in other languages, and play with it. Jabari Zakiya -- See Exclusive Videos: 10th Annual Young Hollywood Awards http://www.hollywoodlife.net/younghollywoodawards2008/
_______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
