Гимназия №1534

Проверка на простоту

Рассмотрим множество натуральных чисел (с нулём) $\{0,\,1,\,2,\,3,\,\ldots\}$. В дальйнейшем под числами будем понимать именно натуральные числа (с нулём). Говорят, что число $n$ делится на число $d$, если найдётся такое число $k$, что $n = kd$. Число $n \ge 2$ называется простым, если оно делится только на само себя и на $1$. В противном случае число $n \ge 2$ называется составным.

Рассмотрим следующую задачу. На вход программе подаётся число $n \ge 2$. Требуется вывести prime, если оно является простым, и composite, если оно является составным.

Эту задачу можно решать, действую «по определению». Это означает, что мы явно проверим, на сколько чисел от $1$ до $n$ делится число $n$. Если делителей окажется ровно $2$, то перед нами простое число, а иначе — составное.

Приведём соответствующий код.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var
  n, num_divisors, i: integer;

begin
  read(n);
  num_divisors := 0; // количество делителей
  
  for i := 1 to n do 
    if n mod i = 0 then
      num_divisors := num_divisors + 1;
  
  if num_divisors = 2 then
    writeln('prime')
  else
    writeln('composite');
end.

Нетрудно понять, что наш алгоритм совершает порядка $n$ действий. Как говорят программисты, наш алгоритм работает за $O(n)$.

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

Теорема. Если число $n$ является составным, то у него имеется делитель $d$ такой, что $2 \le d \le \sqrt{n}$.

Доказательство. Предположим, что утверждение теоремы неверно. Это значит, что есть такое составное число $n$, все делители которого не лежат среди чисел $2,\,3,\,\ldots,\,\sqrt{n}$. Поскольку число $n$ составное, то найдутся такие $a$ и $b$, что $n = ab$. По предположению, $a \gt \sqrt{n}$ и $b \gt \sqrt{n}$, откуда $ab \gt \sqrt{n} \cdot \sqrt{n}$, т. е. $ab \gt n$. Мы пришли к противоречию.

Доказанная нами теорема позволяет вести цикл в строке 8 нашего алгоритма от 2 до $\sqrt{n}$. Таким образом, время работы нашего оптимизированного алгоритма составит $O(\sqrt{n})$, что позволит быстро проверять на простоту числа порядка $10^{16}$. Напомним, что для хранения таких чисел в Паскале следует использовать тип int64, а в C++ — long long.

Алгоритм Евклида

Определение. Число $d$ называется наибольшим общим делителем двух чисел $a$ и $b$, если $d$ делит $a$ и $b$, причём является наибольшим из подобных чисел. Обычно пишут $d = $ НОД$(a, b)$.

Пример: