Question

1. Дано натуральное число n. Проверить, является ли оно простым. Построить блок схему

Answer 1

==============================

                  AKS-Test.

==============================

Обычно, когда проводят тест на простоту сталкиваются с тем, что определить простоту числа в большинстве тестов можно лишь с некоторой вероятностью.

Но математика не стоит на месте и сравнительно недавно появился AKS-тест, позволяющий быстро и гарантированно определить, является ли число простым.

Суть метода такова. Пусть число, которое мы тестируем обозначается A. У нас есть такое выражение: $(x - 1)^A - (x^A - 1)$. Если раскрыть скобки и привести это дело к многочлену вида $k_1*x^A + k_2*x^{A-1} + ... + k_{A-2}*x^2 + k_{A-1}*x + k_{A}$ и все коофиценты k в этом многочлене делятся на A без остатка, то число А - простое. Без вариантов.

Блок-схема с числом n представлена на рисунке 1.

В цикле:  $C = \frac{N!}{Z!(N-Z)!}$. (! - факториал)

P.S. В блок-схеме есть элемент вида (А). Он использовался для связи, так как места на стрелку справа не оказалось. Можешь их убрать и соединить освободившиеся места стрелкой.