440,781 Members | 1,134 Online
Need help? Post your question and get tips & solutions from a community of 440,781 IT Pros & Developers. It's quick & easy.

# Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

 P: n/a 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/9...1/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). See my paper for what/why is going on here. 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 C/C++ gurus will do good implementations. The methodology is very simple, since all I do is additions, multiplications, and array reads/writes. I would also like to the C implementations benchmarked against the versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The C code is here: http://cr.yp.to/primesgen.html Have fun with the code. ;-) Jabari Zakiya Jun 27 '08 #1
5 Replies

 P: n/a On Jun 13, 1:27*pm, jzakiya >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 C/C++ gurus will do good implementations. *The methodology is very simple, since all I do is additions, multiplications, and array reads/writes. I would also like to the C implementations benchmarked against the versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The C code is here: http://cr.yp.to/primesgen.html Have fun with the code. *;-) Jabari Zakiya CORRECTION: http://cr.yp.to/primegen.html NOT "primesgen" Jun 27 '08 #2

 P: n/a On Jun 13, 8:27 pm, jzakiya Not related to ISO C. Try another newsgroup. Jun 27 '08 #3

 P: n/a On Jun 13, 10:27*am, jzakiya >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 C/C++ gurus will do good implementations. *The methodology is very simple, since all I do is additions, multiplications, and array reads/writes. I would also like to the C implementations benchmarked against the versions create by Daniel J Bernstein of the Sieve of Atkin (SoA). The C code is here: http://cr.yp.to/primesgen.html I might give it a go. Bernstein's primegen is not your best competition. This is: http://www.primzahlen.de/files/referent/kw/sieb.htm Here is output using a single 3 GHz CPU: Microsoft Windows [Version 6.0.6001] Copyright (c) 2006 Microsoft Corporation. All rights reserved. C:\math\sieve\ecprime\x64\Release 64>ecprime 100000000000 100% primes: 4118054813 time: 60.153 sec C:\math\sieve\ecprime\x64\Release 64> So your mark is to beat sieving through 100 billion in a minute. I might give your algorithm a crack (no promises though). I set follow-ups to news:comp.programming Jun 27 '08 #4

 P: n/a jzakiya 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/9...1/sharing.html .... snip ... Ruby and Python are not C. This is comp.lang.c, and other languages are off-topic. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: Try the download section. ** Posted from http://www.teranews.com ** Jun 27 '08 #5

 P: n/a On Jun 13, 2:01*pm, CBFalconer

### This discussion thread is closed

Replies have been disabled for this discussion.