Численные алгоритмы

Делители и простые числа

Перебор делителей

Целое число $n \geq 2$ называется простым, если его единственные положительные делители суть 1 и $n$; если у него есть другой делитель, оно составное; 0 и 1 не относятся ни к тем, ни к другим. Определение сразу подсказывает алгоритм: пробовать каждого кандидата $d$ от 2 до $n - 1$ и объявлять число составным, как только один из них его разделит. Это цикл наименьшего делителя из урока Циклы, и он правилен. Однако для простого числа из десяти цифр он выполняет почти десять миллиардов делений, и почти все они бесполезны, по следующей причине.

Отсюда следует, что число делений уменьшается примерно с $n$ примерно до $\sqrt{n}$: для $n$ порядка двух миллиардов это с двух миллиардов до сорока шести тысяч. Программа использует шаблон флага из урока Проектирование правильных циклов: isPrime сначала истинна, и цикл сбрасывает её, если находит делитель.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("Число {} простое", n);    } else {        std::println("Число {} не простое", n);    }}

2147483647

Число 2147483647 простое

Три решения заслуживают комментария. Флаг инициализируется выражением n >= 2, так что 0, 1 и отрицательные числа объявляются непростыми без входа в цикл: забыть этот случай есть типичная ошибка, потому что при $n = 1$ цикл не делает ни одной итерации и программа объявила бы 1 простым. Условие for состоит из двух частей: флага, который останавливает цикл на первом делителе, и границы. А граница записана как d <= n / d, что для положительных целых равносильно $d^2 \leq n$ (целочисленное деление отбрасывает дробную часть, но $d$ не превосходит усечённого частного ровно тогда, когда не превосходит $n/d$, потому что $d$ целое). Число из входных данных, $2^{31} - 1$, есть наибольшее значение int, и оно простое; программа устанавливает это за $46\,339$ остатков, остатков от деления на кандидатов от 2 до $46\,340$.

Инвариант цикла таков: ни одно целое от 2 до $d - 1$ не делит $n$, пока флаг остаётся истинным. Он верен при входе, когда промежуток от 2 до 1 пуст; он сохраняется, потому что если $d$ не делит $n$, то промежуток пополняется числом, которое не делит; а при выходе с истинным флагом инвариант и ложное условие, $d^2 > n$, вместе говорят, что ни один кандидат до $\sqrt{n}$ не делит $n$, а это и требует предложение. Вариант цикла есть количество кандидатов, которые осталось перебрать, то есть целых чисел между $d$ и $\sqrt{n}$: оно уменьшается на единицу за итерацию и не опускается ниже нуля.

Условие, которое переполняется

Естественный способ записать границу есть d * d <= n, и это ошибка. С теми же входными данными цикл доходит до $d = 46\,341$, и тогда произведение $46\,341^2 = 2\,147\,488\,281$ превосходит максимум int.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Простое? {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Санитайзер неопределённого поведения останавливает программу на произведении. Без него знаковое переполнение есть неопределённое поведение, и стандарт не говорит, что происходит. То, что наблюдается с GCC в Linux, с оптимизацией и без неё, поучительно: произведение «заворачивается» и оказывается отрицательным или меньшим $n$, а поскольку ни одно значение int не превосходит максимума, условие d * d <= n больше никогда не становится ложным; цикл продолжает перебирать кандидатов около двух миллиардов итераций, пока не дойдёт до $d = n$, которое делит $n$, и программа объявляет составным простое число. Ошибка переполнения проявляется не как переполнение, а как неверный ответ. Форма d <= n / d переполниться не может, потому что делит вместо того, чтобы умножать; урок Биты и математическая библиотека предлагал другой выход, вычислить границу один раз с помощью std::sqrt, но тогда точность границы зависит от округления в арифметике с плавающей точкой, а у целочисленного деления этой проблемы нет.

Урок «Простые числа и основная теорема арифметики» курса «Алгебра и геометрия I» доказывает, что каждое целое число, большее 1, единственным образом раскладывается в произведение простых; перебор делителей есть самый прямой способ найти это разложение: делить $n$ на каждый найденный делитель и продолжать с частным.