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

0 голосов
36 просмотров

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


Информатика (22 баллов) | 36 просмотров
0

Забавный вопрос :D

Дан 1 ответ
0 голосов

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

                  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. В блок-схеме есть элемент вида (А). Он использовался для связи, так как места на стрелку справа не оказалось. Можешь их убрать и соединить освободившиеся места стрелкой.


image
(7.0k баллов)
0

Тест простоты - не тривиальная задача