CODEWITHSUNDEEP
rubysieve-of-eratosthenes
Damian
Damian

Reputation: 663

Sieve of Eratosthenes in Ruby

Rather than scraping a Ruby version of this algorithm off the net I wanted to create my own based on its description here. However I cannot figure out two things

def primeSieve(n)
  primes = Array.new

  for i in 0..n-2
   primes[i] = i+2
  end

  index = 0
  while Math.sqrt(primes.last).ceil > primes[index]
    (primes[index] ** 2).step(primes.length - 1, primes[index]) 
      {|x| x % primes[index] == 0 ? primes.delete(x) : ""}
    index += 1
  end

  primes
end
  1. Why it doesn't iterate to the end of the array?
  2. According to the description in the link above the loop should be broken out of when the squareroot of the last element in the array is greater than the current prime - mine does this one before.

I'm fairly sure it has something to do with the delete operation modifying the length of the array. For example my function currently yields 2,3,5,7,9,10 when I enter n=10 which is obviously not correct. Any suggestions on how I can go about alterating this to make it work like it's supposed to?

Upvotes: 15

Views: 8124

Answers (5)

shin
shin

Reputation: 32721

This is a reference for those who are interested. The code is from this site.

This code uses Sieve of Eratosthenes as well.

n = 1000000
ns = (n**0.5).to_i + 1
is_prime = [false, false] + [true]*(n-1)
2.upto(ns) do |i|
  next if !is_prime[i]
  (i*i).step(n, i) do |j|
    is_prime[j] = false
  end
end

count = 0
list = (0..n).map do |i|
  count += 1 if is_prime[i]
  count
end

while gets
  puts list[$_.to_i]
end

And here is another one.

def eratosthenes(n)
  nums = [nil, nil, *2..n]
  (2..Math.sqrt(n)).each do |i|
    (i**2..n).step(i){|m| nums[m] = nil}  if nums[i]
  end
  nums.compact
end

p eratosthenes(100)

Upvotes: 1

pjammer
pjammer

Reputation: 9577

or 

x = []
Prime.each(123) do |p|
  x << p
end

There may be a way to use inject here but the inception thing hurts my head today.

Upvotes: 0

nes1983
nes1983

Reputation: 15756

This is a pretty straightforward implementation of the Wikipedia article pseudocode, using a bit array.

#!/usr/bin/env ruby -w

require 'rubygems'
require 'bitarray'

def eratosthenes(n)

   a = BitArray.new(n+1)

   (4..n).step(2) { |i|
      a[i] = 1
   }

   (3..(Math.sqrt(n))).each { |i|
       if(a[i] == 0)
           ((i*i)..n).step(2*i) { |j|
               a[j] = 1
           }
       end
   }
   a
 end

def primes(n)
    primes = Array.new
     eratosthenes(n).each_with_index { |isPrime, idx|
        primes << idx if isPrime == 0
     }
     primes[2..-1]
end

Upvotes: 3

Mike Woodhouse
Mike Woodhouse

Reputation: 52326

There's a faster implementation at www.scriptol.org:

def sieve_upto(top)
  sieve = []
  for i in 2 .. top
    sieve[i] = i
  end
  for i in 2 .. Math.sqrt(top)
    next unless sieve[i]
    (i*i).step(top, i) do |j|
      sieve[j] = nil
    end
  end
  sieve.compact
end

I think it can be improved on slightly thus:

def better_sieve_upto(n)
  s = (0..n).to_a
  s[0] = s[1] = nil
  s.each do |p|
    next unless p
    break if p * p > n
    (p*p).step(n, p) { |m| s[m] = nil }
  end
  s.compact
end

...largely because of the faster array initialisation, I think, but it's marginal. (I added #compact to both to eliminate the unwanted nils)

Upvotes: 17

Andru Luvisi
Andru Luvisi

Reputation: 25328

The following seems to work. I took out the floating point arithmetic and squared instead of square rooting. I also replaced the deletion loop with a "select" call.

while primes[index]**2 <= primes.last
      prime = primes[index]
      primes = primes.select { |x| x == prime || x%prime != 0 }
      index += 1
end

Edit: I think I figured out how you're trying to do this. The following seems to work, and seems to be more in line with your original approach.

while Math.sqrt(primes.last).ceil >= primes[index]
    (primes[index] * 2).step(primes.last, primes[index]) do
      |x|
      primes.delete(x)
    end
    index += 1
end

Upvotes: 5

Related Questions