I am trying to write a code for the following problem:
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.
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.
return false if number == 1
(2..number-1).each do |n|
return false if number % n == 0
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
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:
The more ranges being processed, the faster the Prime::EratosthenesGenerator method should be.