CODEWITHSUNDEEP
rubymathprimes
Zoran
Zoran

Reputation: 4226

Ruby - method for generating prime numbers

I'm writing a method - prime_numbers - that, when passed a number n, returns an n number of primes. It should not rely on Ruby's Prime class. It should behave like so:

prime_numbers 3
=> [2, 3, 5]
prime_numbers 5
=> [2, 3, 5, 7, 11]

My first attempt at this method is as follows:

def prime_numbers(n)
  primes = []
  i = 2

  while primes.length < n do
    divisors = (2..9).to_a.select { |x| x != i }
    primes << i if divisors.all? { |x| i % x != 0 }
    i += 1
  end
  primes
end

Edit: As pointed out, the current method is at fault by being limited to take into account divisors only up to 9. As a result, any perfect square composed of two equal primes greater than 9 is treated as a prime itself.

If anyone has input or tips they can share on better ways to approach this, it would be greatly appreciated.

Upvotes: 0

Views: 1732

Answers (3)

Vitalii Elenhaupt
Vitalii Elenhaupt

Reputation: 7326

In Ruby 1.9 there is a Prime class you can use to generate prime numbers, or to test if a number is prime:

require 'prime'

Prime.take(10) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Prime.take_while {|p| p < 10 } #=> [2, 3, 5, 7]
Prime.prime?(19) #=> true

Prime implements the each method and includes the Enumerable module, so you can do all sorts of fun stuff like filtering, mapping, and so on.

Upvotes: 0

Jason Adrian Bargas
Jason Adrian Bargas

Reputation: 254

Got a good idea for your implementation:

@primes = []
def prime_numbers(n)
  i = 2
  while @primes.size < n do
    @primes << i if is_prime?(i)
    i += 1
  end
  @primes
end

def is_prime?(n)
  @primes.each { |prime| return false if n % prime == 0 }
  true
end

This is based on the idea that non-prime numbers have prime factors :)

Upvotes: 1

mdh1665
mdh1665

Reputation: 46

Note that if the number is composite it must have a divisor less than or equal to $\sqrt{n}$. So you really only have to check up to $sqrt{n}$ to find a divisor.

Upvotes: 2

Related Questions