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

Answer 1

Для начала, вместо того чтобы начать поиск с 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.

Answer 2

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;

Это должно быть достаточно быстро ... Обратите внимание, нет необходимости проверять на простое число ...

Answer 3

На самом деле, в этом случае вам не нужно проверять первичность, просто удалите найденные факторы. Начните с n == 2 и сканируйте вверх. Когда зло-большое число% n == 0, разделите зло-большое число на n и продолжайте с меньшим числом зла. Остановитесь, когда n> = sqrt (число большого зла).

Не должно занимать более нескольких секунд на любой современной машине.

Answer 4

Хотя в вопросе задается наибольший простой множитель, это не обязательно означает, что вы должны сначала найти его ...

Answer 5

Вам нужно уменьшить количество проверок, которые вы делаете ... подумайте, какие цифры вам нужно проверить.

Для лучшего подхода прочтите Сито Эратфосфена ... оно должно направить вас в правильном направлении.

Answer 6

Что касается причины принятого ответа нифа:

Это нормально для проблемы в Эйлере, но не делает это эффективным решением в общем случае. Почему бы вам попробовать четные числа для факторов?

• Если n четное, сдвинуть влево (разделить на 2) пока его больше нет. Если это один, то 2 является наибольшим простым фактор.
• Если n не четное, вам не нужно проверить четные числа.
• Это правда, что вы можете остановиться на SQRT (п).
• Вы должны только проверять простые числа для факторы. Это может быть быстрее, чтобы проверить k делит п, а затем проверить его хотя для простоты.
• Вы можете оптимизировать верхний предел муха, когда вы найдете фактор.

Это привело бы к некоторому коду, подобному этому:

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)

Есть некоторые тесты по модулю, которые являются излишними, так как n никогда не может быть разделено на 6, если все факторы 2 и 3 были удалены. Вы можете разрешить только простые числа для меня.

В качестве примера рассмотрим результат для 21:

21 не является четным, поэтому мы переходим к циклу for с верхним пределом sqrt (21) (~ 4.6). Затем мы можем разделить 21 на 3, поэтому result = 3 и n = 21/3 = 7. Теперь нам осталось протестировать только до sqrt (7). который меньше 3, так что мы закончили с циклом for. Мы возвращаем максимум n и результат, который равен n = 7.

Answer 7

Как только вы найдете ответ, введите в браузере следующее;)

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

Wofram Alpha - твой друг

Answer 8

То, как я это сделал, - поиск простых чисел (p), начиная с 2 с использованием сита Эратосфена. Этот алгоритм может найти все простые числа до 10 миллионов за <2 с на прилично быстрой машине. </p>

Для каждого простого числа, которое вы найдете, тест делите его на число, с которым вы тестируете, до тех пор, пока вы больше не сможете делать целочисленное деление. (т. е. проверьте n % p == 0 и если true, то разделите.)

Однажды n = 1, все готово. Последнее значение n, которое было успешно разделено, является вашим ответом. В сводке вы также нашли все основные факторы n в пути.

PS: Как отмечалось ранее, вам нужно искать только простые числа между 2 <= n <= sqrt(p). Это делает Сито Эратосфена очень быстрым и простым в реализации алгоритмом для наших целей.

Answer 9

Это решение на C ++ заняло 3,7 мс на моем Intel Quad Core i5 iMac (3,1 ГГц)

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

Answer 10

Easy Peasy в 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;
}