代码优化-生成素数 [英] Code Optimization - Generating Prime Numbers

查看:122
本文介绍了代码优化-生成素数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

I am trying to write a code for the following problem:

输入

输入以一行中的测试用例数t(t <= 10)。在接下来的t行中的每行中,都有两个数字m和n(1 <= m <= n <= 1000000000,n-m <= 100000)用空格隔开。

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.

输出

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

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.

示例输入:

2
1 10
3 5

样本输出:

2
3
5
7

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

代码运行良好,唯一的问题是它正在使用与其他编程语言相比,在大输入范围内运行会花费很多时间。

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?

我尝试过使用for循环,普通循环,创建数组然后进行打印。
任何建议。

I have tried using a for loop, normal loop, creating an array and then printing it. Any suggestions.

推荐答案

如果数字为2,则返回true;如果该数字可以被2整除,则返回false。

Return true if the number is 2, false if the number is evenly divisible by 2.

从3开始迭代,而不是从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

这将更快,但仍然不是非常快,如@Technation所解释。

This will be much faster, but still not very fast, as @Technation explains.

这里是如何使用Eratosthenes筛网内置到 Ruby中。您需要预先计算所有素数到最大最大值,这将很快,然后选择每个范围内的素数。

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

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

Here's how the various solutions perform with the range 50000 200000:


  • 您最初的素数?函数:1m49.639s

  • 我修改过的素数?函数:0m0.687s

  • Prime :: EratosthenesGenerator:0m0.221s

更多范围被处理时,Prime :: EratosthenesGenerator方法应该更快。

The more ranges being processed, the faster the Prime::EratosthenesGenerator method should be.

这篇关于代码优化-生成素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆