Ruby素数分解错误

Question

我用ruby做了一个主要的因式分解程序。它可以解决8-9位数字，但当我在程序中添加一个10位数字时，它不能解决问题。对于debug，我编写了循环中的所有步骤，程序求解，但没有完成。它将永远运行。代码如下：

require 'prime'
primSzamok = [1767172329]

def prim_dem(n)
  base = n / 2
  pf = Array.new
  i = 2
    while i <= base
      if Prime.prime?(i)
        while n % i == 0
          pf << i
          n /= i
          puts "i: #{i}, base: #{base}, n: #{n}"
        end
      end
      i += 1
    end
  return pf
end

haromCount = 0

primSzamok.each do |number|
  primArr = prim_dem(number)
  primString = "["

  iCount = 0
  primArr.each do |v|
    if iCount == 0
      primString += "#{v}"
    else
      primString += ", #{v}"
    end

    if v == 3
      haromCount += 1
    end

    iCount += 1
  end
  primString += "]"

  puts "Number: #{number} | Primes: #{primString}"
end

Answer 1

你不需要检查(n/2)数，检查sqrt(n)，因为sqrt(n) * sqrt(n) = n意味着在最坏的情况下，大素数会分解成两个中等大小的素数，否则n本身就是素数，迭代到n/2数会花费太多时间。

将基址更改为base = sqrt(n)

require 'prime'
primSzamok = [1767172329]

def prim_dem(n)
  base = sqrt(n)
  pf = Array.new
  i = 2
    while i <= base
      if Prime.prime?(i)
        while n % i == 0
          pf << i
          n /= i
          puts "i: #{i}, base: #{base}, n: #{n}"
        end
      end
      i += 1
    end
  return pf
end

haromCount = 0

primSzamok.each do |number|
  primArr = prim_dem(number)
  primString = "["

  iCount = 0
  primArr.each do |v|
    if iCount == 0
      primString += "#{v}"
    else
      primString += ", #{v}"
    end

    if v == 3
      haromCount += 1
    end

    iCount += 1
  end
  primString += "]"

  puts "Number: #{number} | Primes: #{primString}"
end