Подходя к решению проблемы Эйлера проекта 3, мое решение правильно?

Question

Задача 3 Project Euler гласит:

Основными факторами 13195 являются 5, 7, 13 и 29. Что является самым большим основным фактором числа 600851475143?

Я сделал это решение, имеет смысл, выглядит хорошо, работает для небольших чисел, но когда мы доходим до огромного числа проблем, это когда программа работает вечно. Мой вопрос, это в корне правильно, и если да, то как я могу оптимизировать код? В моем понимании проблемная функция is_prime ().

bool is_factor(long long int num, long long int factor)
{
    if(!(num%factor))
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool is_prime(long long int num)
{
    long long int i;
    bool flag = true;
    for(i = 2; i <= num/2; i++)
    {
        if(!(num%i))
        {
            flag = false;
        }
    }
    return flag;
}

int main(void)
{
    long long int i, max_factor = 1;
    for(i = 1; i < 600851475143; i++)
    {
        if(is_factor(600851475143,i) && is_prime(i) && i>max_factor)
        {
            max_factor = i;
        }
    }
    printf("%d\n",max_factor);
    return 0;
}

Answer 1

Общая стратегия, которую вы используете на высоком уровне, выглядит следующим образом:

1. Попробуйте разделить целевое число на все числа, меньшие или равные половине целевого числа.
2. Каждый раз, когда вы найдете делитель, посмотрите, является ли оно простым числом и больше ли максимального множителя. Если это так, обновите максимальный коэффициент.
3. Верните наибольшее число, которое вы найдете таким образом.

Учитывая, что ваша цель состоит в том, чтобы найти наибольший множитель одного числа, это довольно разумная стратегия. Есть несколько способов ускорить это. Некоторые из них отражены в комментариях, в то время как другие (насколько мне известно) не были там предложены.

Оптимизация 1: устранение проверки на первичность

Прямо сейчас вы продолжаете делить целевое число на каждый возможный делитель, а затем проверяете, являются ли эти делители простыми числами. Если в вашем целевом числе много делителей, вы потратите много времени на проверку делителей, которые не являются простыми, что сожрет ваше время выполнения.

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

Почему это?

Чтобы понять почему, подумайте, как это будет работать. Сначала вы проверите, делит ли число 2 на число. Если это так, вы разделите столько копий на 2, сколько возможно, а это означает, что если вы попытаетесь в дальнейшем разделить на любое число, кратное 2, вы обнаружите, что большее число не является делителем.

Аналогично, вы затем проверите, делит ли 3 число. Если это так, вы разделите все копии на 3, поэтому никакое число, кратное трем, никогда не разделит оставшееся число.

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

Оптимизация 2: ранняя остановка

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

Вышеприведенная стратегия четкого разделения всех основных факторов, с которыми вы сталкиваетесь, имеет дополнительное преимущество. Предположим, что после всех выполненных делений оставшееся целевое число равно n. Теперь представьте, что ваш текущий делитель d и d <<code>n. Если d делит n, то вы можете написать n как произведение двух чисел d и n / d. Поскольку вы делите целевое число на все основные факторы, с которыми вы сталкиваетесь, мы гарантируем, что n не имеет простых факторов меньше, чем d. Это, в свою очередь, означает, что если n / d <<code>d, то d не может быть делителем n. Зачем? Потому что, если d делит n, то число n / d должно иметь простой множитель меньше d, но мы знаем, что n не имеет таких простых факторов.

В результате, когда вы пробуете делители, вы можете остановиться, как только n / d <<code>d, или, что эквивалентно, как только n <<code>d ², Как только это произойдет, вы знаете, что n больше не имеет никаких простых факторов меньше, чем он сам, поэтому оставшееся число n является последним простым делителем.

На практике это значительно ускорит процесс. Ваше целевое число составляет примерно 10 ¹² , и вы можете остановиться, как только последний делитель будет примерно равен квадратному корню из этого числа, который составляет около 10 ⁶ . Это означает, что вам нужно искать только миллион делителей, а не триллион!

Оптимизация 3: Интеллектуальный выбор делителей

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

Прямо сейчас, например, половина чисел, на которые вы пытаетесь разделить цель, является четной. Помимо 2, четное число не является простым, поэтому вы можете рассмотреть разбиение цикла на две части: специальный случай для обработки 2 и цикл, который начинает считать с 3 и выполняет шаги размера 2 (3, 5, 7, 9, 11, 13 и т. Д.), А не по шагам размера 1. (Глядя на целевое число, вы можете видеть, что оно не четное, поэтому вы можете даже пропустить деление на 2 полностью!)

Еще лучше рассмотреть возможность загрузки списка всех простых чисел примерно до 10 ⁷ . Либо жестко запишите этот список в вашу программу, либо скопируйте все в текстовый файл и прочитайте его при запуске программы. Затем только разделите цель на числа в этом списке. Вуаля! Теперь вы делитесь только на простые числа, что экономит ваше время и силы. (Теорема о простых числах гласит, что только около 10 ln 10 ⁷ & as; 18,4 числа меньше 10 ⁷ будут простыми числами, так что это, вероятно, даст вам дополнительное 20-кратное ускорение поверх все остальное.

Надеюсь, это поможет!