# Prime sieve optimization

**URL:** <https://www.ruby-forum.com/t/prime-sieve-optimization/70315>\
**Category:** Ruby\
**Created:** [September 28, 2006, 5:22am UTC](https://www.ruby-forum.com/t/prime-sieve-optimization/70315 "2006-09-28T05:22:50Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [September 28, 2006, 5:22am UTC](https://www.ruby-forum.com/t/prime-sieve-optimization/70315/1 "2006-09-28T05:22:50Z")

</div>

The prime sieve of Atkin ([Sieve of Atkin - Wikipedia](http://en.wikipedia.org/wiki/Sieve_of_Atkin))  
is, if done right, faster than the sieve of Eratosthenes. I’ve  
included a reimplementation of the mathn Prime class using this sieve,  
but it’s slower than the one in ruby 1.9.

If anyone wants to try their hand at improving this (or starting anew  
if this is a bad start), feel free. Perhaps we can beat the one in  
ruby 1.9 so we can replace it before 1.9 (1.10 ?) becomes the stable  
version.

class Prime\_Atkin  
include Enumerable

# @@next\_to\_check is a multiple of 12.

@@next\_to\_check = 240

# @@primes should contain all primes in 1…@@next\_to\_check

@@primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,  
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,  
163,167,173,179,181,191,193,197,199,211,223,227,229,233,239]

# @@primes\_squared = @@primes.map { |prime| prime\*\*2 }[2…-1]

@@primes\_squared = [25,49,121,169,289,361,529,841,961,1369,1681,  
1849,2209,2809,3481,3721,4489,5041,5329,6241,6889,7921,9409,  
10201,10609,11449,11881,12769,16129,17161,18769,19321,22201,  
22801,24649,26569,27889,29929,32041,32761,36481,37249,38809,  
39601,44521,49729,51529,52441,54289,57121]

# SieveWidth is a multiple of 12.

# Ensure that @@next\_to\_check + SieveWidth \<= @@primes\_squared.last

SieveWidth = 56880  
@@new\_primes = Array.new(SieveWidth, false)  
def initialize  
@index = -1  
end

def succ  
@index += 1  
while @index \>= @@primes.length  
range\_end = @@next\_to\_check + SieveWidth  
high\_x = Math.sqrt(range\_end).floor

```
  1.upto(high_x) do |x|
    x_sq = x**2
    low_y = @@next_to_check - 4*x_sq
    if low_y < 1
      low_y = 1
    else
      low_y = Math.sqrt(low_y).ceil
    end
    high_y = [Math.sqrt(3*x_sq - @@next_to_check),

```

Math.sqrt(range\_end - 3\*x\_sq)].max.floor

```
    high_y.downto(low_y) do |y|
      y_sq = y**2
      n = 4*x_sq + y_sq - @@next_to_check
      @@new_primes[n] = (not @@new_primes.at(n)) if (n >= 0 and n <

```

SieveWidth and (n % 12 == 1 or n % 12 == 5))  
n -= x\_sq  
@@new\_primes[n] = (not @@new\_primes.at(n)) if (n \>= 0 and n \<  
SieveWidth and n % 12 == 7)  
n -= 2\*y\_sq  
@@new\_primes[n] = (not @@new\_primes.at(n)) if (n \>= 0 and n \<  
SieveWidth and x \> y and n % 12 == 11)  
end  
end

```
  @@primes_squared.each do |prime_squared|
    multiple_index = prime_squared *

```

(@@next\_to\_check/prime\_squared).ceil - @@next\_to\_check  
while multiple\_index \< SieveWidth  
@@new\_primes[multiple\_index] = false  
multiple\_index += prime\_squared  
end  
end

```
  @@new_primes.each_with_index do |prime_test, index|
    if prime_test
      prime = @@next_to_check + index
      @@primes << prime
      @@primes_squared << prime**2
    end
  end

  @@next_to_check = range_end
  @@new_primes.fill false
end
@@primes.at @index

```

end  
alias next succ

def each  
loop do  
yield succ  
end  
end  
end

---

<div class="post-metadata">

**Author:** ![C\_Erler](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/a183cd/32.png) [@C\_Erler](https://www.ruby-forum.com/u/C_Erler)\
**Post date:** [September 28, 2006, 5:46am UTC](https://www.ruby-forum.com/t/prime-sieve-optimization/70315/2 "2006-09-28T05:46:54Z")

</div>

If I do all the sieving in one stretch, a naive implementation of the  
Atkin sieve is actually faster than the Prime class in ruby 1.9. The  
Prime class has to do it in blocks (it never knows quite how many  
primes someone will ask for), and it seems that I’ve handled that  
reorganization badly.

Here is a naive, all-in-one-stretch version (faster than Prime in 1.9)  
:

limit = 500000  
primes = Array.new(limit + 1) { false }

(1…limit \*\* 0.5).each do |x|  
x\_sq = x**2  
(1…limit \*\* 0.5).each do |y|  
y\_sq = y**2  
n = 4_x\_sq + y\_sq  
primes[n] = (not primes[n]) if (n \<= limit and (n % 12 == 1 or n %  
12 == 5))  
n = 3_x\_sq + y\_sq  
primes[n] = (not primes[n]) if (n \<= limit and n % 12 == 7)  
n = 3\*x\_sq - y\_sq  
primes[n] = (not primes[n]) if (n \<= limit and x \> y and n % 12 ==  
11)  
end  
end

primes.each\_index do |i|  
primes[i] =  
if primes[i]  
i\_sq = i\*\*2  
i\_sq.step(limit, i\_sq) do |prime\_square\_mult|  
primes[prime\_square\_mult] = false  
end  
i  
else  
nil  
end  
end

primes[2] = 2  
primes[3] = 3  
primes.compact!