代码优化 - 生成素数-Java 学习之路

-1

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

输入

输入以单行中的测试用例数t开始（t <= 10） . 在接下来的t行中的每一行中，存在由空格分隔的两个数m和n（1 <= m <= n <= 1000000000，n-m <= 100000） .

产量

对于每个测试用例，打印所有质数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循环，普通循环，创建一个数组然后打印它 . 有什么建议 .

2 回答

0
如果数字为2，则返回true;如果数字可被2整除，则返回false .

开始迭代3，而不是2.使用两步 .

迭代到数字的平方根，而不是数字减1 .
```
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解释说，这会快得多，但仍然不会很快 .

以下是使用Sieve of Eratosthenes built into Ruby的方法 . 您需要将所有素数预先计算到最大值，这将非常快，然后选择每个范围内的素数 .
```
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方法应该越快 .
回复于 2024-04-28T15:43:31+08:00
2
Ruby比其他语言慢，取决于你比较它的语言;肯定比C / C慢 . 但是你的问题不是语言（尽管它会影响运行时行为），而是你找到素数的方法 . 有许多更好的算法可用于查找素数，例如Sieve of Eratosthenes或Sieve of Atkin . 您还可以阅读维基百科上的“Generating Primes”页面，并按照其中的链接进行操作 .

顺便说一句，对于Eratosthenes的Sieve，甚至还有一个随时可用的piece of code on Stackoverflow . 我相信一点点谷歌搜索也会出现其他算法的实现 .

由于您的问题是在一定范围内找到素数，因此在上面的链接中找到的Sieve of Eratosthenes代码经过修改以适合您的特定问题：
```
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”的变化 .
回复于 2024-04-28T15:43:31+08:00

代码优化 - 生成素数

2 回答

相关问题