Алгоритмы для простых чисел — введение

Приветствую всех🔥, с возвращением! 😎

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

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


Первый алгоритм таков:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;
    }

    if (cnt >= 3) return 0;

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}

Войти в полноэкранный режим Выйти из полноэкранного режима

Это самое простое решение. Оно точно следует математическому определению простых чисел — простое число имеет ровно два делителя. Мы выполняем итерацию от 1 до достижения нашего числа, пытаясь найти, сколько делителей существует. Если их больше 2, мы возвращаем 0(false) или 1(true), если число делителей меньше 2. Это хороший подход, если вы новичок в алгоритмах.

Мы итерируем весь интервал между 1 и числом, переданным в качестве аргумента. Это дало нам линейную сложность, O(n). Хотя это звучит хорошо, для некоторых чисел мы проводим бесполезный анализ.

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

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long cnt{ 0 };

    for (unsigned long long i = 1; i <= Number; ++i)
    {
        if (Number % i == 0) ++cnt;

        if (cnt >= 3) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}



Войти в полноэкранный режим Выйти из полноэкранного режима

Наша сложность все еще не уменьшается, но это стоит оптимизации, которая делает наш код лучше.

Мы можем продолжить наши улучшения, не начиная итерацию с 1, потому что мы знаем, что 1 является делителем для любого числа. Кроме того, мы можем итерировать только до половины числа, потому что мы считаем его делители, а делители числа можно найти до половины числа. В этом случае мы можем избавиться от счетчика делителей, потому что мы начинаем с 2 и останавливаемся на половине, поэтому достаточно найти только один делитель, чтобы сказать, что число не является простым. Таким образом, наш код будет выглядеть следующим образом:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i <= Number / 2; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}

Вход в полноэкранный режим Выйти из полноэкранного режима

Спойлер: наша временная сложность не изменилась. Это по-прежнему линейный алгоритм.
Почему?
Потому что мы делаем O(n/2) шагов, а если мы перепишем это как O(1/2 * n), то 1/2 — это константа, а константы нас не волнуют, поэтому мы их убираем, и получаем O(n).

Другая оптимизация заключается в том, чтобы выполнять итерации до квадратного корня из числа. Мы знаем, что делители числа находятся попарно, поэтому если мы не найдем делителей между [2, квадратный корень из числа], то не найдем и делителей из [квадратный корень из числа, число]. Код будет выглядеть следующим образом:

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    for (unsigned long long i = 2; i * i <= Number; ++i)
    {
        if (Number % i == 0) return 0;
    }

    return 1;
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Теперь временная сложность изменилась. Она стала O(sqrt(n)), потому что мы итерируем над sqrt(n) числами. Даже если мы исключим 1, что будет O(sqrt(n) — 1), 1 — это константа, поэтому нам все равно. Поэтому мы ее удаляем.

Обратите внимание, что мы использовали i * i <= n вместо sqrt(n). Это потому, что sqrt(n) — функция, требующая времени на выполнение, и мы предпочитаем избежать этого времени, вызвав sqrt(n). Еще хуже будет написать цикл for следующим образом for (unsigned long long i = 1; i <= sqrt(Number); ++i). Если написать код таким образом, то на каждой итерации будет повторяться вызов функции sqrt(), что приведет к потере времени и производительности. Конечно, вы можете вызвать sqrt() один раз, сохранить его в переменной и написать что-то вроде этого

unsigned long long square = sqrt(Number);
for (unsigned long long i = 1; i <= square; ++i)
Войти в полноэкранный режим Выйти из полноэкранного режима

Но все равно у нас есть еще один вызов функции, который требует времени. Более чистый и лучший способ — использовать метод i * i <= Number.

Теперь я покажу окончательный вариант.

  1. Во-первых, мы знаем, что 0 и 1 не являются простыми числами.
  2. Во-вторых, мы знаем, что все четные числа, кроме 2, не являются простыми.
  3. В-третьих, мы видим, что достаточно итерации до квадратного корня из числа.
#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    if (Number == 0 || Number == 1) return 0;

    else if (Number % 2 == 0 && Number != 2) return 0;

    else
    {
        for (unsigned long long i = 3; i * i <= Number; i += 2)
        {
            if (Number % i == 0) return 0;
        }
    }

    return 1;

}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}
Вход в полноэкранный режим Выход из полноэкранного режима

Мы итерируем сразу 2 числа, потому что начинаем с 3, а если мы будем итерировать сразу 1 число, то будем итерировать и четные числа, но мы уже проверили четность нашего числа на предыдущем шаге.

Наблюдение: Этот алгоритм обычно используется для конкурсов и олимпиад.

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

#include <iostream>
using namespace std;


bool IsPrime(unsigned long long Number)
{
    unsigned long long divisor = 2;

    while (Number > 1)
    {
        unsigned long long power = 0;

        if (Number % divisor == 0)
        {
            Number /= divisor;
            ++power;
        }

        if (power) return false;

        ++divisor;

        if (divisor * divisor > Number) return true;
    }
}


int main()
{

    unsigned long long number; cout << "Enter number: "; cin >> number; cout << 'n';

    IsPrime(number) == 1 ? cout << "Primen" : cout << "Not primen";

    return 0;
}
Вход в полноэкранный режим Выход из полноэкранного режима

Временная сложность здесь составляет O(sqrt(n)) в дробящем случае. Потому что в лучшем случае число является степенью делителя, например, Number = m^k, где m = 1, 2, 3, 4,... и мы выполняем k делений, что составляет O(log(n)).


Наконец, мы закончили.

Может быть много других улучшений для алгоритмов, которые я показал, и много других алгоритмов для проблемы первичности, но я думаю, что это хорошее введение. В следующий раз я покажу вам еще один интересный алгоритм под названием «Решето Эратосфена», который используется для нахождения всех простых чисел в заданном интервале. В качестве бонуса я покажу вам, как этот алгоритм можно объединить с алгоритмом выше для проверки первичности числа. Это будет сложный и увлекательный алгоритм.


  • Эмануэль Русу

  • Вы можете посетить мой GitHub

  • Или вы можете найти меня на Linkedin

  • Следующая тема: Решето Эратосфена

  • Увидимся в следующий раз! 👋

Оцените статью
Procodings.ru
Добавить комментарий