奇数顺序排列

Question

我写这篇文章是为了求一个数的质因数分解 num。它给出了正确的答案（例如，num 72 的答案是 2, 3, 2, 3, 2），但结果的顺序很奇怪。我不知道为什么。我想知道是否有人看到了我没有看到的东西。

$primes = [2]
$factors = []
num = 72
max = num

def isprime(n)
 $primes.each do |x|
  if n % x == 0 then
   return
  end
 end
 $primes.push(n)
 return
end

i = 3
while i <= max
 isprime(i)
 i += 1
end

while !($primes.include?(num))
 $primes.each do |x|
  if num % x == 0 then
   $factors.push(x)
   num /= x
  end
 end
end
$factors.push(num)

puts $factors

Answer 1

您需要在找到一个因子后立即中断 $primes.each 循环，否则每次都会完成循环。

while !($primes.include?(num))
  $primes.each do |x|
    if num % x == 0 then
      $factors.push(x)
      num /= x
      break
    end
  end
end
$factors.push(num)

P.S：我只关注算法方面而忽略了Ruby方面。

Answer 2

你的内部循环是这样工作的。假设您正在测试数字 72.
您的素数数组将是 [2,3,5,7...]

在第一次迭代的 $primes.each do |x| loop 中，它将针对 2 测试 num = 72 并将其添加到 factor 数组

Inner Iteration 1 => factors = [2], x = 2 , num = 36
Inner Iteration 2 => factors = [2,3], x = 3 , num = 12
Inner Iteration 3 => factors = [2,3], x = 5 , num = 12
Inner Iteration 3 => factors = [2,3], x = 7 , num = 12
Inner Iteration 3 => factors = [2,3], x = 11, num = 12

现在存在内部迭代并且素数循环再次从 2 开始。

Inner Iteration 1 => factors = [2,3,2], x = 2 , num = 6
Inner Iteration 2 => factors = [2,3,2,3], x = 3 , num = 2

内循环再次开始

Inner Iteration 1 => factors = [2,3,2,3,2], x = 2 , num = 2

您必须在内部循环中中断以执行第一个因式分解并退出。

while !($primes.include?(num))
 $primes.each do |x|
  if num % x == 0 then
   $factors.push(x)
   num /= x
   break
  end
end

奇数顺序排列

Array in an odd order

ruby

algorithm

primes

prime-factoring

factorization