3
\$\begingroup\$

Is there a shorter or maybe a cleaner way of doing:

Using your is_prime? method, write a new method, primes that takes a (non-negative, integer) number max and returns an array of all prime numbers less than max.

def is_prime?(max)
  i = 2
  while i < max
    is_divisible = ((max % i) == 0)
    if is_divisible
      # divisor found; stop and return false!
      return false
    end

    i += 1
  end

  # no divisors found
  true
end
def primes(max)
  primes_arr = []

  i = 2
  while i < max
    if is_prime?(i)
      # i is prime; add it to the array
      primes_arr << i
    end

    i += 1
  end

  # return primes_arr
  primes_arr
end
\$\endgroup\$
1

3 Answers 3

1
\$\begingroup\$

Same logic, a bit cleaner and more rubular:

def is_prime?(num)
  (2...num).each do |divisor|
    return false if num % divisor == 0
  end

  true
end

def primes(max)
  primes = []

  (2...max).each do |num|
    primes << num if is_prime?(num)
  end

  primes
end
\$\endgroup\$
3
1
\$\begingroup\$

Here it is using Prime#prime?:

Suppose I want to get all the prime numbers less than 9

require 'prime'

a = (1..12).to_a
p a.select{|e| e.prime? and e < 9 }
# >> [2, 3, 5, 7]

Here is a method

require 'prime'

def prime_below_max(a,max)
   a.select{|e| e.prime? and e < max }
end

ary = (1..12).to_a
p prime_below_max(ary,9)
# >> [2, 3, 5, 7]
\$\endgroup\$
3
  • \$\begingroup\$ The OP is supposed to write the methods for one of the online Ruby quizzes, not take advantage of built-in classes. While this is shorter on the surface it skirts the issue of working with the OPs code to optimize it. \$\endgroup\$ Nov 4, 2013 at 9:20
  • \$\begingroup\$ @theTinMan I thought OP asked us to provide a short and simple code...Now I got what was he looking for... Should I delete this? \$\endgroup\$
    – Arup Rakshit
    Nov 4, 2013 at 9:26
  • 1
    \$\begingroup\$ Prime.each(100).to_a is even shorter \$\endgroup\$
    – steenslag
    Nov 17, 2013 at 19:42
0
\$\begingroup\$

I rewrote is_prime?. It's more robust (doesn't fail when n < 2) and has caching and basic tests.

require 'set'

# Returns true if a number is found to be prime and caches it for quick lookup.
# Uses the simple trial division method.
def is_prime?(n)
  @primes ||= Set.new  # Prefer set over array because of constant-time checks.
  return true if @primes.include?(n)
  return false if n < 2

  (2...n).each do |i|
    return false if n % i == 0
  end

  @primes.add(n)
  true
end

def run_tests
  tests = {
    -1 => false,
    0 => false,
    1 => false,
    2 => true,
    3 => true,
    4 => false,
    5 => true,
    9 => false,
    913 => false,
    997 => true,
    3571 => true,
  }

  tests.each do |num, is_prime|
    # Tests primality.
    if is_prime?(num) == is_prime
      print "PASS: "
    else
      print "FAIL: "
    end
    if is_prime then puts "#{num} is prime" else puts "#{num} is not prime" end

    # Tests caching of primes.
    if is_prime && @primes.include?(num)
      print "PASS: "
    elsif !is_prime && [email protected]?(num)
      print "PASS: "
    else
      print "FAIL: "
    end
    if is_prime then puts "#{num} should be cached" else puts "#{num} should not be cached" end
    puts
  end
end

run_tests

If you need a better primality test (in Ruby) I recommend the Prime class, or if that's not possible for whatever reason, implement the Sieve of Eratosthenes algorithm.

\$\endgroup\$
3
  • \$\begingroup\$ You only cache the fact that certain numbers are prime, but not the fact that other numbers are non-prime. That guarantees a low cache hit rate. \$\endgroup\$ Jan 15, 2015 at 11:57
  • \$\begingroup\$ @200_success that's a good point, thanks for bringing that up. The set can be changed to a hash. The tradeoff is that it would be faster at the expense of taking up more space (which is usually worth it). \$\endgroup\$
    – Dennis
    Jan 15, 2015 at 12:03
  • \$\begingroup\$ Note that you can also speed up trial division by iterating up to sqrt(n). E.g. 2.upto(Math.sqrt(n).to_i) do |i| \$\endgroup\$
    – Dennis
    Jan 15, 2015 at 12:10