Некоторые древние способы проверки чисел на простоту:

• Решето Эратосфена. 12 Алгоритм по нахождению простых чисел, разработанный греческим математиком Эратосфеном. 1 Суть метода в последовательном отсеивании составных чисел, начиная с числа 2, которое является первым простым числом. 3 Эратосфен записывал все числа от одного до какого-то числа, а потом вычёркивал единицу и числа, кратные двум (4, 6, 8 и т. д.). 4 Первым оставшимся числом после двух было 3. 4 Далее вычёркивались через два все числа, идущие после трёх (числа, кратные 3, то есть 6, 9, 12 и т. д.). 4 В конце концов оставались невычеркнутыми только простые числа. 4
• Пробное деление. 1 Чтобы выяснить, является ли многозначное число простым или составным, нужно хорошо знать признаки делимости чисел и таблицу умножения. 1 Для выполнения пробного деления проверяемое число делят на все простые числа от 2 до квадратного корня из этого числа. 1 Если число ни на какое другое, кроме единицы и самого числа, больше не делится, значит, оно относится к множеству простых чисел. 1