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

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

Answer 2

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

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 3

вы можете захотеть увидеть это: Существует ли простой алгоритм, который может определить, является ли X простым, и не запутать простого смертного программиста?

а мне нравится раствор грязи лилии:

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

Я это проверил здесь

Answer 4

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

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

Answer 6

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