代码优化——生成质数

Question

我正在尝试为以下问题编写代码：

输入

输入以单行中的测试用例数t开始（t<=10）。在接下来的 t 行中，有两个数字 m 和 n（1 <= m <= n <= 1000000000，n-m<=100000），由 space.

分隔

输出

对于每个测试用例打印所有素数 p 使得 m <= p <= n，每行一个数字，用空行分隔测试用例。

示例输入：

2
1 10
3 5

示例输出：

我的代码：

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

代码运行没问题，我遇到的唯一问题是，与其他编程语言相比，运行针对大输入范围需要花费大量时间。

我是不是做错了什么？能否进一步优化此代码以获得更快的运行时间？

我试过使用 for 循环、普通循环、创建数组然后打印它。任何建议。

Answer 1

Return 如果数字是 2，则为真，如果数字能被 2 整除，则为假。

从 3 开始迭代，而不是 2。使用两个步长。

迭代到数字的平方根，而不是数字减一。

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

正如@Technation 解释的那样，这会快得多，但仍然不是很快。

以下是使用埃拉托色尼筛法 built into Ruby 的方法。您需要预先计算所有素数直到最大最大值，这将非常快，然后 select 每个范围内的素数。

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

以下是各种解决方案在 50000 200000 范围内的表现：

你原来的素数？功能：1m49.639s
我修改过的素数？功能：0m0.687s
Prime::EratosthenesGenerator: 0m0.221s

处理的范围越多，Prime::EratosthenesGenerator 方法应该越快。

Answer 2

Ruby 比其他一些语言慢，具体取决于您将其与哪种语言进行比较；肯定比 C/C++ 慢。但是您的问题不是语言（尽管它会影响运行时间行为），而是您寻找素数的方式。有很多更好的算法可以找到素数，例如维基百科上的 Sieve of Eratosthenes or the Sieve of Atkin. You might also read the “Generating Primes” 页面，然后跟随 link 那里。

顺便说一下，对于埃拉托色尼筛法，甚至还有现成的 piece of code on Whosebug。我敢肯定，通过谷歌搜索也能找到其他算法的实现。

由于您的问题是在一定范围内找到素数，因此这是在上面找到的埃拉托色尼筛法代码 link 修改以适合您的特定问题：

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

注意从 "sieve.compact" 到具有相应条件的复杂 "sieve.reject" 的变化。

代码优化——生成质数

Code Optimization - Generating Prime Numbers

ruby

algorithm

primes