473,320 Members | 1,982 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)

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 2243
On Jun 13, 1:27*pm, jzakiya <jzak...@gmail.comwrote:
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
CORRECTION:

http://cr.yp.to/primegen.html NOT "primesgen"
Jun 27 '08 #2
On Jun 13, 8:27 pm, jzakiya <jzak...@gmail.comwrote:
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.
<snip>
Not related to ISO C. Try another newsgroup.
Jun 27 '08 #3
On Jun 13, 10:27*am, jzakiya <jzak...@gmail.comwrote:
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
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
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]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Jun 27 '08 #5
On Jun 13, 2:01*pm, CBFalconer <cbfalco...@yahoo.comwrote:
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.
That's true, and his request (to build a version in C to see how it
compares to other sieves) is also off topic.
However, Ruby and Python were not the gist of his post {more like an
aside}, so he may deserve censure, but certainly not for that.

In my previous post I made a forward to news:comp.programming which is
more appropriate. There is a contests newsgroup also, but it does not
seem very active and this is not really a contest either.
Jun 27 '08 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: lostinpython | last post by:
I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n > 2 is prim if no number between 2 and sqrt of n...
32
by: Cmorriskuerten | last post by:
HI, is this is this solution to test if a number is a prime number or not: /* * Is n a prime number? * Return TRUE (1): n is a prime number * Return FALSE (0): n is a *not* a prime number...
19
by: swisscheese | last post by:
I figured someone out there must have written a minimal code size prime number generator. I did not find one after a bit of searching around. For primes up to 100 the best I could do was 70...
25
by: johnmsimon | last post by:
i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is...
10
by: Joel Mayes | last post by:
Hi All; I'm teaching myself C, and have written a prime number generator. It is a pretty inefficient implementation of the Sieve of Eratosthenes to calculate primes up to 1,000,000. If anyone...
60
by: rhle.freak | last post by:
Here is my code to generate prime numbers.It works absolutely fine when the range is *not very large*. However on initializing i with a large integer it produces erroneous results (some numbers...
2
Blackout
by: Blackout | last post by:
Hi, I'm having problems with this C program. Whenever I run it, it doesn't print anything. The program is supposed to compute and display all the prime numbers from 1 - 300 using the sieve of...
8
by: cokofreedom | last post by:
I was reading up on this site http://www.noulakaz.net/weblog/ 2007/03/18/a-regular-expression-to-check-for-prime-numbers/] of an interesting way to work out prime numbers using Regular Expression....
3
by: jzakiya | last post by:
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...
4
by: jzakiya | last post by:
Update: 2008/11/03 Architecture & coding improvements. Renamed generators. I am 90% finished writing up a mathematical analysis of my method. In the process I found an architectural...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.