我如何对大数进行素分解？

Question

我正在尝试解决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 ++我的代码有什么问题，我该如何改进？

Answer 1

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

Answer 2

但是problem指出您只需要找到600851475143的最大质数，对吗？为什么不从sqrt（600851475143）迭代到2并返回第一个为质数的数字？

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;
}