Ответ на комментарий:
Можете объяснить в новой статье: Что такое простые числа?
Прошу простым человеческим языком. Как для супер двоечника. Что только я не перечитал, везде одно и тоже, как под копирку. Ну не понимаю я. Хотя мне это очень интересно. В этом есть что то магическое.
Понятно что это число, которое больше 1 (единицы). Ну так они все больше единицы, кроме ее самой.
Чисел много. Очень много. Их для удобства нужно классифицировать, разделять на группы по одному общему признаку. Сейчас таких признаков в математике - вагон и маленькая тележка. Один из признаков числа - простота.
Признак простых чисел - невозможность его разделить нацело на любое другое натуральное число, кроме как на само себя и на 1.
Признак, выраженный через "не" - один из самых паршивых не только для математика, но и для жизни вообще. Подумайте сами: вот мы видим, что число 51 не делится на 2. Видим, что на 3 тоже не делится (ладно, ладно, уговорили, делится). Проверяем 4. И так далее.
И так что, все делители перебирать?
Да, потому что нет других способов узнать, простое у нас число 999 или нет. Мы обязаны доказать (а сделать это можно только перебором) что у 999 нет делителей. На 2 - не делится, а вот на 3 уже делится (333 получится). Значит, 999 - не простое число, а другое. И вообще, тут было видно, что 9+9+9=27 2+7=9, а 9 делится на три, значит 999 тоже (это называют признаками делимости). То есть, в общем случае можно показать, что число не является простым, но нельзя доказать, что оно простое, не перебрав все числа в качестве делителей.
Алгоритмов проверки чисел на простоту великое множество. В статье Красота математических закономерностей, я показал картинку, для создания которой использовал алгоритм, реализованный на python. Он сначала проверял чётность испытуемого числа, потом начинал перебирать все делители с шагом 2, начиная с 3 до квадратного от него. Любой остаток от деления, который был бы равен нулю возвращал False. Алгоритм не оптимальный, медленный (да и питон сам по себе не отличается производительностью), но все числа до 4 000 000 проверил меньше, чем за минуту.
Конечно, на больших числах этот алгоритм будет работать долго.
Надеюсь, теперь стало понятнее, что такое простое число. Однако вопрос в комментарии был несколько шире, чем просто определение (которое неплохо описано и в википедии). Вопрос:
Зачем вообще выделять простые числа?
Вообще выделение простых чисел - очень любопытная задача сама по себе. Но такая классификация имеет и практическое значение. В частности, в школе приходится сталкиваться с сокращением дробей. И вот тут появляются проверки на простоту и более сложная проверка - двух чисел на взаимную простоту.
То есть, тут как... Если мы установили, что число (в числителе или знаминателе) является простым, то мы можем дальше не тратить время на подбор делителя - их нет. Но! Большое НО! Установить это мы можем, только потратив кучу времени на перебор делителей. Меняем шило на мыло, получается. Так вот, для упрощения этой операции в классе математики всегда висит таблица простых чисел в пределах 1000.
Достаточно просто поднять глаза, и убедиться, что твоё число простое, значит, нет смысла искать другие делители.
Но если число больше 1000, то нужно проверять делители.
Практической ценности проверка на простоту действительно больших чисел не несёт, так как в реальной жизни мы просто не можем оперировать числами, больше чем 10⁸⁸ степени (по оценкам учёных, если мы пересчитаем все элементарные частицы во всей известной нам Вселенной, то получим число, записывающееся с помощью всего 88 десятичных цифр). И всё же проверка 88-значного числа займёт очень много времени. Но если мы спустимся с Небес на Землю, то, например, мне за всю жизнь только один раз потребовалась проверка чисел за пределами первого столбца таблицы с рисунка. Именно тогда, когда я рисовал скатерть Улама. И за меня это великолепно сделал компьютер.