Sieve of Eratosthenes in Ruby

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

Sieve of Eratosthenes variant

def primes(n)
  nums = (2..n)
  not_prime = []
  primes = []
  nums.to_a.each_with_index do |it, idx|
      next if not_prime.include?(it)
      primes << it 
      ((primes.last)..n).step(primes.last).each_with_index do |num, idx|
        next if idx == 0 || num == primes.last
        not_prime << num
      end
  end

  primes
end

Algorithm - What is wrong with this Sieve of Erastothenes solution

To test primality of a given number n you need to check whether it's divisible by any of the primes <= sqrt(n). Since you have hardwired the primes up to 17 into it, your algorithm will only work for values of n <= 17².

On top of that, you included 9 in your list of "primes". This shouldn't affect your test except for the value 9 itself, since anything divisible by 9 is also divisible by 3, but it's quite naughty.

Improving efficiency of my Sieve of Eratosthenes in Ruby?

You could skip the loop where mult is not a prime number.

def sieve(upper)
  i = 0
  list = (2..upper).to_a
  (2..Math.sqrt(upper)).each do |mult|
    if list[i] #proceed only when mult is prime
      init = mult + i
      (init..upper-1).step(mult) do |index|
        list[index] = nil
      end
    end
    i += 1
  end
  list.compact
end

This trims down the runtime from 1.9 to 0.7 secs on my machine. I'm sure there's a lot more that can be done, though.

Why is my implementation of Atkin sieve is slower than Eratosthenes?

As Wikipedia says, "The modern sieve of Atkin is more complicated, but faster when properly optimized" (my emphasis).

The first obvious place to save some time in the first set of loops would be to stop iterating over y when 4*x**2 + y**2 is greater than n. For example, if n is 1,000,000 and x is 450, then you should stop iterating when y is greater than 435 (instead of continuing to 999 as you do at the moment). So you could rewrite the first loop as:

for x in (1..Math.sqrt(n/4).truncate)
    X = 4 * x ** 2
    for y in (1..Math.sqrt(n - X).truncate)
        k = X + y ** 2
        sieve[k] = !sieve[k] if k%12 == 1 or k%12 == 5
    end
end

(This also avoids re-computing 4*x**2 each time round the loop, though that is probably a very small improvement, if any.)

Similar remarks apply, of course, to the other loops over y.

A second place where you could speed things up is in the strategy for looping over y. You loop over all values of y in the range, and then check to see which ones lead to values of k with the correct remainders modulo 12. Instead, you could just loop over the right values of y only, and avoid testing the remainders altogether.

If 4*x**2 is 4 modulo 12, then y**2 must be 1 or 9 modulo 12, and so y must be 1, 3, 5, 7, or 11 modulo 12. If 4*x**2 is 8 modulo 12, then y**2 must be 5 or 9 modulo 12, so y must be 3 or 9 modulo 12. And finally, if 4*x**2 is 0 modulo 12, then y**2 must be 1 or 5 modulo 12, so y must be 1, 5, 7, 9, or 11 modulo 12.

I also note that your sieve of Eratosthenes is doing useless work by testing divisibility by all primes below i. You can halt the iteration once you've test for divisibility by all primes less than or equal to the square root of i.

Trying to create an array with N first primes numbers

It looks like you're trying to implement the Sieve of Eratosthenes, modified to return a certain number of primes rather than check a certain number of candidates, but there's several problems with your approach.

You start with 2 as prime, but start your search at 1. You're going to get 1 and 2 again. Your search should start at 3.

You're correct that you can gain efficiencies by iterating two at a time, but you've left 2 out of your sieve so even numbers remain. Your candidates and your divisors both need to be odds only.

Your check to see if you've matched enough primes is in the outermost loop, so it's never going to stop the inner loop.

@num should be passed in as an argument.

Cleaning that all up, and extracting the inner loop as a function to simplify things...

# Pass in the number of primes to make the function more useful. Default to @num.
def find_prime_array(num_primes = @num)
  # Start with 2 so we only have to check odd numbers.
  array_prime = [2]

  # Step through only the odd numbers.
  (3..2001).step(2) do |i|
    # Extract the prime check into a function.
    array_prime << i if prime?(i)

    # Stop when we have enough primes.
    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i)
  # Also only divide by only the odd numbers.
  (3..(i-1)).step(2) do |j| 
    return false if i % j == 0
  end
  
  return true
end

But we can do this more efficiently. The power of the sieve is you don't have to divide every candidate by every odd number. You only need to divide by the primes you've found so far.

def find_prime_array(num_primes = @num)
  array_prime = [2]

  (3..2001).step(2) do |i|
    array_prime << i if prime?(i, array_prime)

    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i, array_prime)
  array_prime.each do |j| 
    return false if i % j == 0
  end
  
  return true
end

Finally, we can do the same thing more idiomatically with no artificial limit.

def find_prime_array(num_primes)
  primes = [2]

  (3..).step(2) do |candidate|
    if primes.none? { |prime| candidate % prime == 0 }
      primes << candidate
    end
    break if primes.size >= num_primes
  end

  return primes
end

Code Optimization - Generating Prime Numbers

Return true if the number is 2, false if the number is evenly divisible by 2.

Start iterating at 3, instead of 2. Use a step of two.

Iterate up to the square root of the number, instead of the number minus one.

def prime?(number)
  return true if number == 2
  return false if number <= 1 or number % 2 == 0
  (3..Math.sqrt(number)).step(2) do |n|
    return false if number % n == 0
  end
  true
end

This will be much faster, but still not very fast, as @Technation explains.

Here's how to do it using the Sieve of Eratosthenes built into Ruby. You'll need to precompute all the primes up to the maximum maximum, which will be very quick, and then select the primes that fall within each range.

require 'prime'

ranges = Array.new(gets.strip.to_i) do
  min, max = gets.strip.split.map(&:to_i)
  Range.new(min, max)
end

primes = Prime.each(ranges.map(&:max).max, Prime::EratosthenesGenerator.new)

ranges.each do |range|
  primes.each do |prime|
    next if prime < range.min 
    break if prime > range.max
    puts prime
  end

  primes.rewind
  puts "\n"
end

Here's how the various solutions perform with the range 50000 200000:

Your original prime? function: 1m49.639s
My modified prime? function: 0m0.687s
Prime::EratosthenesGenerator: 0m0.221s

The more ranges being processed, the faster the Prime::EratosthenesGenerator method should be.

How do I efficiently sieve through a selected range for prime numbers?

I haven't looked fully, but one factor is that, you are replacing a certain value in primes with nil, and later compact-ing it to remove them. This is a waste. Just by doing that directly with delete_at makes it more than twice fast:

def ranged_sieve2(l, b)
  primes = (l..b).to_a
  primes.delete_at(0) if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes.delete_at(index) if index
    end
  end
  primes
end

ranged_sieve(1, 100) # => Took approx 8e-4 seconds on my computer
ranged_sieve2(1, 100) # => Took approx 3e-4 seconds on my computer

Another point to improve is that, using a hash is much faster than array as the relevant size gets larger. Replacing your array implementation with a hash, you can get this:

def ranged_sieve3(l, b)
  primes = (l..b).inject({}){|h, i| h[i] = true; h}
  primes.delete(0)
  primes.delete(1)
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      primes.delete(stepped)
    end
  end
  primes.keys
end

When you do range_sieve3(1, 100) with this, it is slower than range_sieve2(1, 100) because of the overhead. But as you make the number larger, the superiority becomes salient. For example, I got this result on my computer:

ranged_sieve(1, 1000) # => Took 1e-01 secs
ranged_sieve2(1, 1000) # => Took 3e-02 secs
ranged_sieve3(1, 1000) # => Took 8e-04 secs

Sieve of Eratosthenes in Ruby