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

Question

我正在尝试解决 Project Euler third question 但是当我尝试使用大数字时我的代码可以完美地处理小数字但它没有给我任何答案。

#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++ 我的代码有什么问题，我该如何改进它？

Answer 1

但是problem说你只需要找到600851475143的最大质数，对吧？你为什么不从 sqrt(600851475143) 迭代到 2 和 return 第一个素数？

bool isPrime(uint64_t num)
{
  bool result = true;
  for(uint64_t i = 2; i < std::sqrt(num); ++i)
  {
    if(num % i == 0)
    {
      result = false;
      break;
    }
  }
  return result;
}

int main()
{
  uint64_t num = 600851475143;
  uint64_t i = std::sqrt(num);
  while (i > 1)
  {
    i--;
    if (num%i != 0) continue;
    if (isPrime(i))
    {
      break;
    }
  }
  std::cout << i << std::endl;
  return 0;
}

当然可以做得更快，但在我的机器上需要 10 毫秒，所以我想这并不糟糕。

Answer 2

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

每次找到一个除数 d，将你的数字除以 d。

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

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

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

这不是一个快速的算法，但是 600851475143 不是一个大数，这个算法可以毫无问题地将它分解。

例如 (on 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 技巧，但你在这里甚至不需要它。如果最高因子很高，它会有所帮助，而在本例中则不是。

Answer 3

#include <iostream>

using namespace std;

typedef long long ulong;

int main()
{
ulong num = 600851475143;
ulong div = num;
ulong p = 0;

ulong i = 2;
while (i * i <= div)
{
    if (div % i == 0)
    {
        div /= i;
        p = i;
    }
    else {
        i++;
    }
}

if (div > p) 
{ 
    p = div;
}

cout << p << endl;

return 0;
}

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

How do I prime factorize large numbers?

c++

algorithm

math

prime-factoring