Тест на простоту

Пусть n – нечетное натуральное число, причем

n – 1 = p₁^e1… p_r^er,

где p₁<…<p_r – простые числа. Если для каждого i=1,2,…,r существует такое целое число b_i (2≤b_i≤n-1), что

b_i^n-1 mod n ≡ 1 и b_i^(n-1)/pi mod n 1,

то n – простое.

Ввод: нечётное натуральное n

Вывод: одно из двух сообщений: «n простое» или «n не простое».

Шаг 1. Получаем разложение n – 1 на r простых множителей и присваиваем i значение 1.

Шаг 2. Если i > r, то вывести сообщение: «n простое», в противном случае присвоим b значение 2 и переходим к шагу 3.

Шаг 3. Если не выполняется условие и и b < n, то переходим к шагу 4, иначе переходим к шагу 5.

Шаг 4. Увеличиваем b на единицу и возвращаемся к шагу 3.

Шаг 5. Если b = n, то вывести сообщение: «n не простое»; в противном случае увеличиваем i на единицу и возвращаемся к шагу 2.