How do I generate the first n prime numbers?

Question

I am learning Ruby and doing some math stuff. One of the things I want to do is generate prime numbers.

I want to generate the first ten prime numbers and the first ten only. I have no problem testing a number to see if it is a prime number or not, but was wondering what the best way is to do generate these numbers?

I am using the following method to determine if the number is prime:

class Integer < Numeric
  def is_prime?
    return false if self <= 1
    2.upto(Math.sqrt(self).to_i) do |x|
      return false if self%x == 0
    end
    true
  end
end

Answer 1

Here's a super compact method that generates an array of primes with a single line of code.

  def get_prime(up_to)
    (2..up_to).select { |num| (2...num).all? { |div| (num % div).positive? } }
  end

Answer 2

I did this for a coding kata and used the Sieve of Eratosthenes.

puts "Up to which number should I look for prime numbers?"
number = $stdin.gets.chomp
n = number.to_i
array = (1..n).to_a

  i = 0

while array[i]**2 < n

i = i + 1
array = array.select do |element|
  element % array[i] != 0 || element / array[i] == 1


end
end

 puts array.drop(1)

Answer 3

def get_prime(number)
  (2..number).each do |no|
      if (2..no-1).all? {|num| no % num  > 0}
        puts no
      end
  end
end

get_prime(100)

Answer 4

class Numeric
  def prime?
    return self == 2 if self % 2 == 0

    (3..Math.sqrt(self)).step(2) do |x|
      return false if self % x == 0
    end

    true
  end
end

With this, now 3.prime? returns true, and 6.prime? returns false.

Without going to the efforts to implement the sieve algorithm, time can still be saved quickly by only verifying divisibility until the square root, and skipping the odd numbers. Then, iterate through the numbers, checking for primeness.

Remember: human time > machine time.

Answer 5

I think this may be an expensive solution for very large max numbers but seems to work well otherwise:

def multiples array
  target = array.shift 
  array.map{|item| item if target % item == 0}.compact
end

def prime? number
  reversed_range_array = *(2..number).reverse_each
  multiples_of_number = multiples(reversed_range_array)
  multiples_of_number.size == 0 ? true : false
end

def primes_in_range max_number
  range_array = *(2..max_number)
  range_array.map{|number| number if prime?(number)}.compact
end

Answer 6

Here is a way to generate the prime numbers up to a "max" argument from scratch, without using Prime or Math. Let me know what you think.

def prime_test max
    primes = []
    (1..max).each {|num| 
        if
            (2..num-1).all? {|denom| num%denom >0}
        then
            primes.push(num)
        end
    }
    puts primes
end

prime_test #enter max

Answer 7

# First 10 Prime Numbers

number = 2
count = 1
while count < 10
  j = 2
  while j <= number
    break if number%j == 0
    j += 1
  end
  if j == number
    puts number 
    count += 1
  end
  number += 1
end

Answer 8

Not related at all with the question itself, but FYI:

• if someone doesn't want to keep generating prime numbers again and again (a.k.a. greedy resource saver)
• or maybe you already know that you must to work with subsequent prime numbers in some way
• other unknown and wonderful cases

Try with this snippet:

  require 'prime'

  for p in Prime::Generator23.new
    # `p` brings subsequent prime numbers until the end of the days (or until your computer explodes)
    # so here put your fabulous code
    break if #.. I don't know, I suppose in some moment it should stop the loop
  end
  fp

If you need it, you also could use another more complex generators as Prime::TrialDivisionGenerator or Prime::EratosthenesGenerator. More info

Answer 9

Implemented the Sieve of Eratosthene (more or less)

def primes(size)
    arr=(0..size).to_a
    arr[0]=nil
    arr[1]=nil
    max=size
    (size/2+1).times do |n|
        if(arr[n]!=nil) then
            cnt=2*n
            while cnt <= max do
                arr[cnt]=nil
                cnt+=n
            end
        end
    end
    arr.compact!
end

Moreover here is a one-liner I like a lot

def primes_c a
    p=[];(2..a).each{|n| p.any?{|l|n%l==0}?nil:p.push(n)};p
end

Of course those will find the primes in the first n numbers, not the first n primes, but I think an adaptation won't require much effort.

Answer 10

Ruby: Print N prime Numbers http://mishra-vishal.blogspot.in/2013/07/include-math-def-printnprimenumbernoofp.html

include Math

def print_n_prime_number(no_of_primes=nil)

  no_of_primes = 100 if no_of_primes.nil?

  puts "1 \n2"

  count = 1

  number = 3

  while count < no_of_primes

sq_rt_of_num = Math.sqrt(number)

number_divisible_by = 2

while number_divisible_by <= sq_rt_of_num

  break if(number % number_divisible_by == 0)

  number_divisible_by = number_divisible_by + 1

end

if number_divisible_by > sq_rt_of_num

  puts number

  count = count+1

end

number = number + 2

  end

end

print_n_prime_number

Answer 11

People already mentioned the Prime class, which definitely would be the way to go. Someone also showed you how to use an Enumerator and I wanted to contribute a version using a Fiber (it uses your Integer#is_prime? method):

primes = Fiber.new do
  Fiber.yield 2
  value = 3
  loop do
    Fiber.yield value if value.is_prime?
    value += 2
  end
end

10.times { p primes.resume }

Answer 12

Check out Sieve of Eratosthenes. This is not Ruby specific but it is an algorithm to generate prime numbers. The idea behind this algorithm is that you have a list/array of numbers say

2..1000

You grab the first number, 2. Go through the list and eliminate everything that is divisible by 2. You will be left with everything that is not divisible by 2 other than 2 itself (e.g. [2,3,5,7,9,11...999]

Go to the next number, 3. And again, eliminate everything that you can divide by 3. Keep going until you reach the last number and you will get an array of prime numbers. Hope that helps.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 13

If you'd like to do it yourself, then something like this could work:

class Integer < Numeric
    def is_prime?
        return false if self <= 1
        2.upto(Math.sqrt(self).to_i) do |x|
            return false if self%x == 0
        end 
        true
    end 

    def next_prime
        n = self+1
        n = n + 1 until n.is_prime?
        n   
    end 
end

Now to get the first 10 primes:

e = Enumerator.new do |y|
    n = 2
    loop do
        y << n
        n = n.next_prime
    end
end

primes = e.take 10

Answer 14

require 'prime'

Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Answer 15

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.