Подтвердить что ты не робот

Справка по проекту Euler Question 3

Я пытаюсь работать через Project Euler, и я нахожу барьер на проблеме 03. У меня есть алгоритм, который работает для меньших чисел, но проблема 3 использует очень и очень большое число.

Проблема 03: Основными факторами 13195 являются 5, 7, 13 и 29. Каков максимальный простой коэффициент числа 600851475143?

Вот мое решение в С#, и оно работает, я думаю, что около часа. Я не ищу ответа, потому что я действительно хочу решить это сам. В основном просто ищут помощь.

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

ОТВЕТЫ

Ответ 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.

Ответ 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;

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Это приведет к следующему коду:

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)

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

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

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

Ответ 7

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

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

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

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

Ответ 9

Использование рекурсивного алгоритма в Java выполняется менее секунды... подумайте о своем алгоритме, так как он включает в себя некоторые "грубые форсировки", которые можно устранить. Также посмотрите, как ваше пространство решения может быть уменьшено путем промежуточных вычислений.

Ответ 10

Легкий peasy в С++:

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

Ответ 11

Это решение на С++ заняло 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;
}

Ответ 12

Все проблемы проекта Эйлера должны занимать меньше минуты; даже неоптимизированная рекурсивная реализация в Python занимает менее секунды [0,09 сек. (cpu 4.3 ГГц)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

Ответ 14

Возможно, это считается обманом, но одна возможность в haskell - написать (для записи я сам написал строки и не проверял потоки eulerproject);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Ответ 15

Попробуйте использовать Тест Primary Miller-Rabin, чтобы проверить, что число является простым. Это должно значительно ускорить процесс.

Ответ 16

Другой подход состоит в том, чтобы сначала получить все простые числа до n/2, а затем проверить, равен ли модуль 0. Алгоритм, который я использую для получения всех простых чисел до n, можно найти здесь.