时间戳

首页 > 解决方案 > 如何对大数进行质因数分解？

c++ - 如何对大数进行质因数分解？

问题描述

我正在尝试解决Project Euler 第三个问题，但是当我尝试使用大数字时，虽然我的代码可以完美地处理小数字，但它并没有给我任何答案。

#include<iostream>

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

int main()
{
   long long int a = 0, bigPrime = 0, smallPrime = 2, prime = 0;
   cout << "Please enter a number...!" << endl;
   cin >> a;

   for(long long int i = 2 ; i < a ; i++)
   {
      for(long long int c = 2 ; c < i ; c++)
      {
         if(i % c != 0)
         {
            prime = i;
         }
         else
         {
            prime = 0;
            break;
         }
      }
      if(prime > 0 )
      {
         if(a % prime == 0)
         {
            bigPrime = prime;
         }
      }

  }


  cout << "The biggest prime is = " << bigPrime << endl;
  return 0;

}

那是我的错误代码:) 我正在使用 ubuntu linux 和 g++ 我的代码有什么问题，我该如何改进它？

标签： c++algorithmmathprime-factoring

解决方案

您可以使用一个简单的技巧来改进您的程序：

每次找到除数d时，将您的数字除以d。

这意味着对于找到的每个除数，您的数字都会变小，从而使剩余部分更容易分解。

作为奖励，这意味着你不需要那么小心只使用素数作为除数。每次找到一个除数，它就是当前数的最小除数，既然是最小除数，它一定是素数。这节省了整个循环级别。

这些因子是按从小到大的顺序提取的，所以最终你拥有的是最高的素因子——这个挑战的答案。

这不是一个快速的算法，但 600851475143 不是一个很大的数字，这个算法不会有问题。

例如（在 ideone 上）：

for (long long int d = 2; d * d <= a; d++) {
    if (a % d == 0) {
        a /= d;
        d--; // this is to handle repeated factors
    }
}

我也使用了旧d * d <= a技巧，但您在这里甚至不需要它。如果最高因子很高，它会有所帮助，而在这个例子中它不是。

推荐阅读