# Printing out prime numbers from an array given a max number

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

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
• Would you happen to know a similar way of printing out the primes up to (max) number without the without using "is_prime" method?
– ZeroOne
Commented Nov 4, 2013 at 7:09
• @ZeroOne something like this? <gist.github.com/micahbf/7299091> Commented Nov 4, 2013 at 7:12
• gist.github.com/micahbf/7299091 Commented Nov 4, 2013 at 7:19

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]
• 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. Commented Nov 4, 2013 at 9:20
• @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?
– Arup Rakshit
Commented Nov 4, 2013 at 9:26
• Prime.each(100).to_a is even shorter Commented Nov 17, 2013 at 19:42

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

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.

• 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. Commented Jan 15, 2015 at 11:57
• @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). Commented Jan 15, 2015 at 12:03
• 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| Commented Jan 15, 2015 at 12:10