-3

我正在尝试使用一个程序来找到 600851475143 的最大素数。这是针对欧拉项目的：http ://projecteuler.net/problem=3

我首先尝试使用以下代码：

    #Ruby solution for http://projecteuler.net/problem=2
    #Prepared by Richard Wilson (Senjai)

    #We'll keep to our functional style of approaching these problems.
    def gen_prime_factors(num) # generate the prime factors of num and return them in an array
      result = []
      2.upto(num-1) do |i| #ASSUMPTION: num > 3
        #test if num is evenly divisable by i, if so add it to the result.
        result.push i if num % i == 0
        puts "Prime factor found: #{i}" # get some status updates so we know there wasn't a crash
      end
      result #Implicit return
    end

#Print the largest prime factor of 600851475143. This will always be the last value in the array so:
puts gen_prime_factors(600851475143).last #this might take a while

这对于小数字非常有用，但对于大数字，这将需要很长时间（和大量内存）。

现在我不久前学习了大学微积分，但我已经很生疏了，从那以后我的数学就没有跟上。

我不想要一个直截了当的答案，但我想指出资源或告诉我需要学习什么来实现我在程序中看到的一些算法。

4

1 回答 1

9

There's a couple problems with your solution. First of all, you never test that i is prime, so you're only finding the largest factor of the big number, not the largest prime factor. There's a Ruby library you can use, just require 'prime', and you can add an && i.prime? to your condition.

That'll fix inaccuracy in your program, but it'll still be slow and expensive (in fact, it'll now be even more expensive). One obvious thing you can do is just set result = i rather than doing result.push i since you ultimately only care about the last viable i you find, there's no reason to maintain a list of all the prime factors.

Even then, however, it's still very slow. The correct program should complete almost instantly. The key is to shrink the number you're testing up to, each time you find a prime factor. If you've found a prime factor p of your big number, then you don't need to test all the way up to the big number anymore. Your "new" big number that you want to test up to is what's left after dividing p out from the big number as many times as possible:

big_number = big_number/p**n

where n is the largest integer such that the right hand side is still a whole number. In practice, you don't need to explicitly find this n, just keep dividing by p until you stop getting a whole number.

Finally, as a SPOILER I'm including a solution below, but you can choose to ignore it if you still want to figure it out yourself.

require 'prime'

max = 600851475143; test = 3

while (max >= test) do
  if (test.prime? && (max % test == 0))
    best = test
    max = max / test
  else
    test = test + 2
  end
end

puts "Here's your number: #{best}"

Exercise: Prove that test.prime? can be eliminated from the if condition. [Hint: what can you say about the smallest (non-1) divisor of any number?]
Exercise: This algorithm is slow if we instead use max = 600851475145. How can it be improved to be fast for either value of max? [Hint: Find the prime factorization of 600851475145 by hand; it's easy to do and it'll make it clear why the current algorithm is slow for this number]

于 2013-05-12T18:46:50.190 回答