c# - Project Euler 问题 3 帮助

Question

我正在尝试通过 Project Euler 工作，但在问题 03 上遇到了障碍。我有一个适用于较小数字的算法，但问题 3 使用了一个非常非常大的数字。

问题03： 13195的质因数是5、7、13和29。600851475143这个数的最大质因数是多少？

这是我在 C# 中的解决方案，我认为它已经运行了将近一个小时。我不是在寻找答案，因为我确实想自己解决这个问题。主要是寻求帮助。

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

score 15 · Accepted Answer

对于初学者，不要从 n / 2 开始搜索，而是从 n 的平方根开始搜索。你会得到一半的因素，另一半是他们的补充。

例如：

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

score 10 · Accepted Answer

虽然这个问题要求最大的主要因素，但这并不一定意味着你必须首先找到那个......

score 10 · Accepted Answer

实际上，对于这种情况，您不需要检查素数，只需删除您找到的因素。从 n == 2 开始向上扫描。当 evil-big-number % n == 0 时，将 evil-big-number 除以 n 并继续使用 small-evil-number。当 n >= sqrt(big-evil-number) 时停止。

在任何现代机器上不应该超过几秒钟。

score 10 · Accepted Answer

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

这应该足够快...注意，无需检查素数...

score 6 · Accepted Answer

你需要减少你正在做的检查量......想想你需要测试什么数字。

为了更好地阅读埃拉托色尼筛法......它应该让你指向正确的方向。

score 3 · Accepted Answer

至于接受 nicf 回答的原因：

Euler 的问题是可以的，但在一般情况下并不能使其成为有效的解决方案。为什么要尝试偶数的因数？

如果 n 是偶数，则左移（除以 2）直到不再是偶数。如果是 1，那么 2 是最大的质因数。
如果 n 不是偶数，则不必测试偶数。
确实，您可以在 sqrt(n) 处停止。
您只需要测试素数的因子。测试 k 是否除 n 然后测试它的素数可能会更快。
当您找到一个因素时，您可以即时优化上限。

这将导致一些这样的代码：

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

有一些模数检验是多余的，因为如果所有因素 2 和 3 都被删除，n 永远不能被 6 整除。你只能允许 i 的素数。

举个例子，让我们看看 21 的结果：

21 不是偶数，所以我们进入上限 sqrt(21) (~4.6) 的 for 循环。然后我们可以将 21 除以 3，因此结果 = 3 和 n = 21/3 = 7。我们现在只需要测试 sqrt(7)。它小于 3，所以我们完成了 for 循环。我们返回 n 的最大值和结果，即 n = 7。

score 2 · Accepted Answer

我这样做的方法是使用 Eratosthenes 筛从 2 开始搜索素数 ( p)。该算法可以在速度相当快的机器上在 <2s 内找到所有 1000 万以下的素数。

对于您找到的每个素数，测试将其划分为您正在测试的数字，直到您不能再进行整数除法。（即检查n % p == 0，如果为真，则除以。）

一次n = 1，你就完成了。成功划分的最后一个值n就是你的答案。在旁注中，您还发现n了途中的所有主要因素。

PS：如前所述，您只需要搜索2 <= n <= sqrt(p). 这使得 Eratosthenes 筛成为一种非常快速且易于实现的算法，用于我们的目的。

score 2 · Accepted Answer

找到答案后，在浏览器中输入以下内容；）

http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)

Wofram Alpha 是你的朋友

score 1 · Accepted Answer

在 Java 中使用递归算法运行时间不到一秒……考虑一下您的算法，因为它包含一些可以消除的“蛮力”。还要看看如何通过中间计算来减少您的解决方案空间。

score 1 · Accepted Answer

C ++中的简单操作：

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

score 1 · Accepted Answer

这个 C++ 解决方案在我的 Intel Quad Core i5 iMac (3.1 GHz) 上花费了 3.7 毫秒

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

score 0 · Accepted Answer

所有 Project Euler 的问题都应该在不到一分钟的时间内完成；即使是 Python 中未优化的递归实现也只需不到一秒 [0.09 秒 (cpu 4.3GHz)]。

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

score 0 · Accepted Answer

你可能想看看这个：有没有一种简单的算法可以确定 X 是否为素数，而不会使普通的程序员感到困惑？

我喜欢 lill mud 的解决方案：

要求“mahn.rb”
将 600851475143.prime_division.last.first

我在这里检查过

score -1 · Accepted Answer

尝试使用Miller-Rabin Primality Test来测试一个数是否为素数。这应该会大大加快速度。

score -1 · Accepted Answer

另一种方法是先让所有素数达到 n/2，然后检查模数是否为 0。我用来让所有素数达到n的算法可以在这里找到。

score -1 · Accepted Answer

也许它被认为是作弊，但在haskell中的一种可能性是写（为了记录，我自己写了这些行并且没有检查eulerproject线程）；

import Data.Numbers.Primes
last (primeFactors 600851475143)

c# - Project Euler 问题 3 帮助

16 回答 16

Related

Reference