Code Optimization - Generating Prime Numbers

Question

I am trying to write a code for the following problem:

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Sample Input:

2
1 10
3 5

Sample Output:

2
3
5
7

3
5

My code:

def prime?(number)
    return false if number == 1
    (2..number-1).each do |n|            
        return false if number % n == 0             
    end 
    true    
end

t = gets.strip.to_i
for i in 1..t
    mi, ni = gets.strip.split(' ')
    mi = mi.to_i
    ni = ni.to_i

    i = mi
    while i <= ni
        puts i if prime?(i)
        i += 1
    end


    puts "\n"
end

The code is running fine, only problem I am having is that it is taking a lot of time when run against big input ranges as compared to other programming languages.

Am I doing something wrong here? Can this code be further optimized for faster runtime?

I have tried using a for loop, normal loop, creating an array and then printing it. Any suggestions.

Answer 1

Ruby is slower than some other languages, depending on what language you compare it to; certainly slower than C/C++. But your problem is not the language (although it influences the run-time behavior), but your way of finding primes. There are many better algorithms for finding primes, such as the Sieve of Eratosthenes or the Sieve of Atkin. You might also read the “Generating Primes” page on Wikipedia and follow the links there.

By the way, for the Sieve of Eratosthenes, there is even a ready-to-use piece of code on Stackoverflow. I'm sure a little bit of googling will turn up implementations for other algorithms, too.

Since your problem is finding primes within a certain range, this is the Sieve of Eratosthenes code found at the above link modified to suit your particular problem:

def better_sieve_upto(first, last)
  sieve = [nil, nil] + (2..last).to_a
  sieve.each do |i|
    next unless i
    break if i*i > last
    (i*i).step(last, i) {|j| sieve[j] = nil }
  end
  sieve.reject {|i| !i || i < first}
end

Note the change from "sieve.compact" to a complexer "sieve.reject" with a corresponding condition.

Answer 2

Return true if the number is 2, false if the number is evenly divisible by 2.

Start iterating at 3, instead of 2. Use a step of two.

Iterate up to the square root of the number, instead of the number minus one.

def prime?(number)
  return true if number == 2
  return false if number <= 1 or number % 2 == 0
  (3..Math.sqrt(number)).step(2) do |n|
    return false if number % n == 0
  end
  true
end

This will be much faster, but still not very fast, as @Technation explains.

Here's how to do it using the Sieve of Eratosthenes built into Ruby. You'll need to precompute all the primes up to the maximum maximum, which will be very quick, and then select the primes that fall within each range.

require 'prime'

ranges = Array.new(gets.strip.to_i) do
  min, max = gets.strip.split.map(&:to_i)
  Range.new(min, max)
end

primes = Prime.each(ranges.map(&:max).max, Prime::EratosthenesGenerator.new)

ranges.each do |range|
  primes.each do |prime|
    next if prime < range.min 
    break if prime > range.max
    puts prime
  end

  primes.rewind
  puts "\n"
end

Here's how the various solutions perform with the range 50000 200000:

• Your original prime? function: 1m49.639s
• My modified prime? function: 0m0.687s
• Prime::EratosthenesGenerator: 0m0.221s

The more ranges being processed, the faster the Prime::EratosthenesGenerator method should be.