On Jun 13, 1:12 pm, jzakiya <[EMAIL PROTECTED]> 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 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 and Ruby and Python source from here: > > http://www.4shared.com/dir/7467736/97bd7b71/sharing.html > > Below is a sample of one of the simple prime generators. I did a > Python version of this in my paper (see Python source too). The Ruby > version below is the minimum array size version, while the Python has > array of size N (I made no attempt to optimize its implementation, > it's to show the method). > > 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 > end > > def primesP3(val): > # all prime candidates > 3 are of form 6*k+(1,5) > # initialize sieve array with only these candidate values > n1, n2 = 1, 5 > sieve = [False]*(val+6) > while n2 < val: > n1 += 6; n2 += 6; sieve[n1] = n1; sieve[n2] = n2 > # now load sieve with seed primes 3 < pi < 6, in this case just 5 > sieve[5] = 5 > > for i in range( 5, int(ceil(sqrt(val))), 2) : > if not sieve[i]: continue > # p1= 5*i, k = 6*i, p2 = 7*i, > p1 = 5*i; k = p1+i; p2 = k+i > while p2 <= val: > sieve[p1] = False; sieve[p2] = False; p1 += k; p2 += k > if p1 <= val: sieve[p1] = False > > primes = [2,3] > if val < 3 : return [2] > primes.extend( i for i in range(5, val+(val&1), 2) if sieve[i] ) > > return primes > > Now to generate an array of the primes up to some N just do: > > Ruby: 10000001.primesP3a > Python: primesP3a(10000001) > > The paper presents benchmarks with Ruby 1.9.0-1 (YARV). I would love > to see my various prime generators benchmarked with optimized > implementations in other languages. I'm hoping Python gurus will do > better than I, though the methodology is very very simple, since all I > do is additions, multiplications, and array reads/writes. > > Have fun with the code. ;-) >
CORRECTION: http://cr.yp.to/primegen.html NOT "primesgen" Jabari Zakiya -- http://mail.python.org/mailman/listinfo/python-list
