ravi - 1 year ago 129
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.

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download