问

Ruby中的项目Euler#3

孤狼舔血_347 发布于 2023-02-08 05:54

项目欧拉问题#3:

13195的主要因素是5,7,13和29. 600851475143中最大的素数是多少？

def is_prime?(number)
    prime = true
    (2...number).each { |x|
        prime = false if number % x == 0
    }
    prime
end

def largest_prime(number)
    primes = []
    (number.downto(1)).each {|x|
        primes.push(x) if number % x == 0 && is_prime?(x)
        break if primes.count == 1
    }
    primes[0]
end

我的答案是用Ruby编写的.该代码适用于较小的数字但不大,任何人都可以解释究竟发生了什么以及如何绕过它？我见过其他人有这个问题 - 抱歉重新发布 - 但我是一个编程新手,我并不真正理解他们的答案,也没有看到任何其他帖子回答Ruby.谢谢!

1 个回答

以下是一些帮助您提高代码性能的指针(假设您的测试编号是n):

仅从进行整除测试2到square_root(n).square_root(n)在此范围内,任何大于已经涵盖的数字 .以数学方式思考:)

任何偶数,这2不是一个素数!

使用主筛可以大大提高主要测试算法的性能.

但是,不要这样做:

因为,你正在解决欧拉问题的乐趣和学习,不要使用primeruby提供的库.

以下是我用过的两个助手来解决这个问题(当我刚开始使用ruby时,我写的很久了,可能效率不高,例如他们不使用sieve我建议的):
```
def lower_divisors_of(n)
  data = (2..(Math.sqrt(n).to_i)).select{ |a| n % a == 0 }
  data.map{|a| [a, n/a]}.flatten.sort.reverse
end

def is_prime?(n)
  lower_divisors_of(n).empty?
end

lower_divisors_of(n).detect{|i| is_prime?(i)}
```
2023-02-08 06:24 回答

年轻的蒲山公_777

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签