ravi ravi - 3 months ago 26
Ruby Question

Code Optimization - Generating Prime Numbers

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.

mwp mwp
Answer

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.

Comments