Как я премьер-факторизовать большие числа? - PullRequest
Новая
       8

Как я премьер-факторизовать большие числа?

0 голосов
/ 30 марта 2020

Я пытаюсь решить 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 ++, что не так с моим кодом и как я могу его улучшить?

Ответы [ 3 ]

2 голосов
/ 30 марта 2020

Вы можете улучшить свою программу, используя один простой трюк:

Каждый раз, когда вы найдете делитель d, делите свое число на d.

Это означает, что для каждого найденного делителя , ваш номер становится меньше, что упрощает разложение оставшейся части.

В качестве бонуса это означает, что вам не нужно быть очень осторожным, используя только простые числа в качестве делителей. Каждый раз, когда делитель найден, он является наименьшим делителем текущего числа, а поскольку это наименьший делитель, он должен быть простым. Это сохраняет весь уровень зацикливания.

Факторы извлекаются в порядке от наименьшего к наивысшему, так что в итоге то, что у вас есть, является наивысшим основным фактором - ответом на этот вызов.

Это не быстрый алгоритм, но 600851475143 не является большим числом, и этот алгоритм не станет его фактором.

Например, на идеоне : 

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 трюк, но он тебе здесь даже не нужен. Помогает, если самый высокий коэффициент высокий, и в этом примере это не так.

0 голосов
/ 30 марта 2020 
#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;
}
0 голосов
/ 30 марта 2020

Но проблема гласит, что вам просто нужно найти наибольшее простое число из 600851475143, верно? Почему бы вам просто не выполнить итерацию с sqrt (600851475143) до 2 и вернуть первое число, которое является простым? 

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 мс, поэтому Я думаю, это не страшно.

...