1

在正常时间段内，我的代码似乎适用于 6-8 位数字。当我输入更大的值时，数量会变得非常荒谬。完成需要4个多小时。这是我的代码。

#Fermat's factorization method

def get_largest_prime n
    t=(Math.sqrt(n)+1).floor
    k=0
    prime_numbers=[]
    while (t+k)<n
        element = (t+k)**2-n
        if is_integer? Math.sqrt(element)
            #store prime numbers
            prime_numbers << t+k+Math.sqrt(element)
            prime_numbers << t+k-Math.sqrt(element) 
            #puts "Prime Factors of #{n} are: #{t+k+Math.sqrt(element)} and #{t+k-Math.sqrt(element)}"
        end
        k+=1
    end
  puts "Prime Factors: "+prime_numbers.to_s 
end

#making sure 450.0 is 450, for example.
def is_integer? number
    number.to_i == number ? true : false
end

get_largest_prime 600851475143

运行此程序将需要 4 个多小时。

但是，例如为值“600851”或“60085167”运行它并不需要很多时间。有什么帮助吗？

4

4 回答 4

2

首先请注意，费马因式分解通常不会为您提供主要因素。

然后，你运行它直到t+k >= n，这意味着你运行while循环n - t时间，因为t大致是sqrt(n)，这是一个O(n)算法。对于n像 600851475143 （大约 6*10^11）这样的大文件，这肯定需要很长时间。

您需要更改算法。当你找到一对除数（都大于 1）时，递归地分解它们。如果找到的因子中较小的一个为 1，则这是一个素因子。

这样做（原谅糟糕的风格，我几乎不知道红宝石）：

#Fermat's factorization method

def get_largest_prime n
    t=(Math.sqrt(n)+1).floor
    k=0
    prime_numbers=[]
    while (t+k)<n
        element = (t+k)**2-n
        if is_integer? Math.sqrt(element)
            #store prime numbers
            a = t+k+Math.sqrt(element)
            b = t+k-Math.sqrt(element)
            if b == 1
                prime_numbers << a
                break
            end
            prime_numbers += get_largest_prime a
            prime_numbers += get_largest_prime b
            break
            #puts "Prime Factors of #{n} are: #{t+k+Math.sqrt(element)} and #{t+k-Math.sqrt(element)}"
        end
        k+=1
    end
  return prime_numbers
end

#making sure 450.0 is 450, for example.
def is_integer? number
    number.to_i == number ? true : false
end

a = get_largest_prime 600851475143
puts "Prime Factors: "+a.to_s

快速解决给定的问题。

但是，对于没有接近平方根的除数的数字，仍然需要很长时间。

试验除法的标准分解具有更好的最坏情况行为（O(sqrt(n)最坏情况）。不过，混合方法可能比纯试除法稍快一些。

于 2013-04-05T14:35:42.213 回答
1

这里有两个效果：

1) 当一个整数在 Ruby 中大于 2**31 时，它使用不同的、更慢的表示

2）一旦数字变得足够大，没有已知的分解算法最终不会表现不佳 - 从技术上讲，它们都比您想要分解的数字（位数）的任何多项式都慢。

你可以通过使用加快速度

Math.sqrt(element)

较少的。在所有测试之前将其结果分配给变量。请注意，这不会“解决”您的问题。最终它不会在某个数字以上运行得足够快 - 即使您将所有内容都转移到 C （尽管您可能会在 C 变慢之前挤出几个额外的数字）

于 2013-04-05T14:20:04.007 回答
0

可能，您可以尝试下面的代码。

def prime_factor limit
    (2..Math.sqrt(limit).to_i).inject([]) do |memo, var|
        memo << var if limit % var == 0 and !memo.any? {|d| var % d == 0}
        memo
    end
end
prime_result = prime_factor 600851475143
puts prime_result.max
于 2014-07-01T14:09:56.043 回答
0

您使用的循环越少，您的代码运行速度就越快；-)（更少的 cpu 周期）。尝试在这个找到最大素数的程序上递归地做所有事情

于 2015-01-11T11:42:37.780 回答