Project Euler Question 3 Help

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

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

Для лучшего подхода, прочитанного на Sieve of Erathosthenes ... он должен заставить вас указывать в правильном направлении.

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

• Если n равно, сдвиг влево (разделите на 2), пока его больше нет. Если это , то тогда 2 является наибольшим простым фактором.
• Если n не равно, вам не нужно проверить четные номера.
• Это правда, что вы можете остановиться на sqrt (n).
• Вам нужно только проверить простые числа для факторов. Возможно, было бы быстрее протестировать , то ли 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) 

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

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

Answer 10

Все проблемы, связанные с проектом Эйлера, должны занимать меньше минуты; даже неоптимизированная рекурсивная реализация в 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 

Answer 11

вы можете увидеть это: Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

и мне нравится решение LILL грязевых в:

требуют "mathn.rb"
ставит 600851475143.prime_division.last.first

Я проверил его here

Answer 12

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 13

После того, как вы нашли ответ, введите в вашем браузере;)

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

Wofram Альфа ваш друг

Answer 14

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

Answer 15

Это решение на 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 16

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

import Data.Numbers.Primes 
last (primeFactors 600851475143)