count_primes.rb

# https://leetcode.com/problems/count-primes/description/

# return the number of prime numbers less than a positive number n
def count_primes(n)
  primes = []
  (2..n-1).each do |i|
    primes[i] = true
  end

  (2..Math.sqrt(n)).each do |i|
    next if primes[i] == false

    j = i * i

    loop do
      break if j >= n

      primes[j] = false

      j += i
    end
  end

  primes.count { |el| el == true }
end

require 'minitest/autorun'

class TestCountPrimes < MiniTest::Test
  def test_it_works
    assert_equal 4, count_primes(9)
    assert_equal 10, count_primes(30)
    assert_equal 114_155, count_primes(1_500_000)
    #[1] pry(main)> Math.sqrt 1_500_000
    #=> 1224.744871391589
  end
end