Ruby - 确定数字是否为素数

Question

我正在运行Project Euler上的问题来自学Ruby编程. 我知道有一个内置函数可以做到这一点,但我正在避免使用内置函数来帮助我学习.

所以我必须编写一个方法来确定一个数字是否是素数.第一种方法有效,但第二种方法没有.有谁能解释为什么？

 def is_prime n
  for d in 2..(n - 1)
   if (n % d) == 0
    return false
   end
  end

  true
 end

 def is_prime2 n
  foundDivider = false
   for d in 2..(n - 1)
    foundDivider = ((n % d) == 0) or foundDivider
   end
  not foundDivider
 end

Answer 1

这是因为=优先级高于or.请参阅下面的Ruby的运算符优先级表(从最高到最低的优先级):

[ ] [ ]=
**
! ~ + -
* / %
+ -
>> <<
&
^ |
<= < > >=
<=> == === != =~ !~
&&
||
.. ...
? :
= %= { /= -= += |= &= >>= <<= *= &&= ||= **=
defined?
not
or and
if unless while until
begin/end

有问题的行被解析为......

(foundDivider = ((n % d) == 0)) or foundDivider

......这当然不是你的意思.有两种可能的解决方案:

强制优先权是你真正的意思......

foundDivider = (((n % d) == 0) or foundDivider)

...或者使用||运算符,其优先级高于=:

foundDivider = ((n % d) == 0) || foundDivider

Answer 2

Ruby带有预定义的类,如Prime.您所要做的就是将该课程纳入您的项目.

require 'prime'

然后,您可以使用一些Prime方法,例如首先获得第一个x prime元素:

Prime.first(5) # Ret => [2, 3, 5, 6, 11]

或者你可以这样做:

Prime.each(100) do |prime|
  p prime # Ret => [2, 3, 5, 7, 11, ..., 97]
end

希望这个对你有帮助.

Answer 3

def prime(n)
  return false if n < 2

  (2..n/2).none?{|i| n % i == 0}
end

素数是除了自身和1之外没有正除数的任何数字.

Answer 4

从循环中查找素数：

def get_prime_no_upto(number)
  pre = [1]
  start = 2
  primes = (start..number).to_a
  (start..number).each do |no|
    (start..no).each do |num|
      if ( no % num  == 0) && num != no
        primes.delete(no)
        break
      end
    end
  end
  pre + primes
end

并使用它如下：

puts get_prime_no_upto(100)

干杯!

Answer 5

def prime? n
  (2..Math.sqrt(n)).none? {|f| n % f == 0}
end

因数范围应从 2 开始，到 n 的平方根结束，因为每个数字都可以被 1 整除，并且没有数字可以被大于其平方根的两个数字整除。

解释：非素数是两个数的乘积。

n = f1 * f2

n总是能被它的平方根整除，因此 和 都f1不能f2大于 n 的平方根，否则f1 * f2会大于n。因此，至少有一个因子小于或最多等于Math.sqrt(n)。在查找素数的情况下，只需要找到一个因子，因此我们应该循环从2到 的平方根n。