Задача: определить, является ли 32-битное число простым (детерминированно) Решение: (на C++) Базы для тестирования. Использование первых 4 простых баз делает тест детерминированным // для всех 32-битных целых чисел. См. https://oeis.org/A014233. int64_t базы[] = {2, 3, 5, 7}; inline int countTrailingZeros(uint64_t n) { if (n == 0) return 64; return __builtin_ctzll(n); } int64_t modularСтепень(int64_t основание, int64_t степень, int64_t модуля) { int64_t res = 1; int64_t b = базовый % модуля; int64_t e = степень; в то время как (e > 0) { если (e & 1) { // Не переполняется, потому что мы предполагаем, что 32-битные целочисленные входы res = (res * b) % модуля; } b = (b * b) % модуль; e >>= 1; } return res; } bool isPrime(int64_t n) { если (n < 2) возвращает false; если (n < 4) возвращает true; если (!