Каков алгоритм нахождения "Простое ли число или составное" без поиска делителя? По математике интерес

Answer 1

Существуют полиномиальные тесты простоты. Но они носят вероятностный характер, т. е. число является простым с определенной вероятностью. И все эти тесты сложны вычислительно (но проще, чем вычислять делители для пятнадцатизначных чисел) .
Примеры. Тест Миллера — Рабина, тест Ферма, Тест Соловея — Штрассена.
Сами тесты описывать не буду, слишком много букофф.

Answer 2

Построить решето Эратосфена.
Выписать все числа строчку; вычеркнуть все чётные числа, кроме самой двойки;
из оставшихся вычеркнуть все делящиеся на 3, кроме самого 3;
из оставшихся вычеркнуть все делящиеся на 5, кроме 5 и т. д.