Доброго времени суток, товарищи! Сегодня мне бы хотелось начать мой канал с довольно простой темы. На канале я собираюсь разбирать разные алгоритмы программирования, стараясь давать их лаконичным и простым языком, по этому же соображению писать я буду на python. Весь код статьи будет прикреплен на github. Ну что ж, давайте приступать!
Простое число - число, которое из делителей имеет только 1 и само себя(например: 2, делится без остатка только на 1 и на 2), грубо говоря ни на что не делится.
Стоит уточнить, что 1 простым числом не считается.
Теперь перейдем к задаче. Нам нужно определить является ли число простым.
Первая идея, которая приходит в голову - перебрать все числа до самого числа и проверять является ли каждое число делителем данного(полный перебор). Это долго, потому что при числе равным 200, мы проверим 200 чисел, а если число уже будет 10^200? Это будет довольно долго.
Алгоритмическая сложность O(n)
Следующая концепция - это как-то ограничить перебор. Но как? Для этого можно заметить, что нам нужно найти хотя бы один делитель, чтобы показать, что число не простое. Но у понятия делитель существует такое свойство: у каждого не простого числа существует делитель(отличный от 1 и самого числа), не превосходящий квадратного корня из числа.
Почему же так? Ведь если число не простое, то оно будет иметь хотя бы один делитель, а этот делитель будет иметь пару(то есть если мы поделим 12 на 2, то 2 будет иметь пару 6, 12 делится и на 2 и на 6, при чем 2*6=12). Пусть это будут числа a и b. Теперь представим, что оба делителя больше квадрата числа. a>sqrt(n), b>sqrt(n), значит, так как sqrt(n)*sqrt(n)=n, то a*b>n, получаем противоречие. Отсюда мы однозначно можем утверждать, что у каждого НЕ простого числа один делитель будет меньше квадрата этого числа. Получается, что если мы не нашли делителя до квадрата, то число является простым.
Теперь уже, если число будет 10^200 мы проверим лишь 10^100 чисел.
Алгоритмическая сложность O(sqrt(n))
Я добавлю, что можно подключать библиотеки и брать квадратный корень из n, округлять и перебирать циклом for до этого числа, но эффективней и проще будет запустить данный цикл while.
Существуют другие способы проверки на простоту(например решето Эратосфена), о которых я поговорю в других статьях, но а для более продвинутых дам ссылку на статью(проверка тестом Ферма), на которую я когда-то наткнулся на просторах интернета и не хочу присваивать себе авторство.