Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
bool prime(long long n)
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Надёжный тест простоты чисел [Numberphile]
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма:
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
bool ferma(long long x) < if(x == 2) return true; srand(time(NULL)); for(int i=0;i<100;i++)< long long a = (rand() % (x — 2)) + 2; if (gcd(a, x) != 1) return false; if( pows(a, x-1, x) != 1) return false; >return true; >
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
long long gcd(long long a, long long b)
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю.
Ее смысл очень похож на быстрое возведение в степень.
long long mul(long long a, long long b, long long m) < if(b==1) return a; if(b%2==0)< long long t = mul(a, b/2, m); return (2 * t) % m; >return (mul(a, b-1, m) + a) % m; > long long pows(long long a, long long b, long long m) < if(b==0) return 1; if(b%2==0)< long long t = pows(a, b/2, m); return mul(t , t, m) % m; >return ( mul(pows(a, b-1, m) , a, m)) % m; >
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Асимптотика решения
Итоговая асимптотика проверки на простоту — O (K * log N * log N), где K — количество итераций теста Ферма, которое обычно равняется 100. Если требуется проверить на простоту число типа int, то можно обойтись без двоичного умножения. Тогда асимптотика проверки на простоту будет равна O (K * log N).
Решение простых задач на python | Високосный ли год
- проверка на простоту
- тест Ферма
- алгоритм
- программирование
- спортивное
- асимптотика
- НОД
- двоичное умножение
- быстрое возведение в степень
- Спортивное программирование
- Алгоритмы
- Математика
Источник: habr.com
Проверка числа на простоту
Программа принимает на вход число и проверяет, простое оно или нет.
Решение задачи
- Принимаем на вход число и записываем его в отдельную переменную.
- Инициализируем переменную, которая будет выполнять роль счетчика, значением 0 .
- Организуем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении).
- Затем находим количество делителей нашего числа. При помощи условного оператора if мы проверяем, делится ли число без остатка, и затем, если делится, увеличиваем наш счетчик на единицу.
- Если число делителей равно 0 , то проверяемое число является простым.
- Выводим результат на экран.
- Конец.
Исходный код
Ниже дан исходный код, который осуществляет проверку числа на простоту. Результаты работы программы также даны ниже.
a = int(input(«Введите число: «)) k = 0 for i in range(2, a // 2+1): if (a % i == 0): k = k+1 if (k
Объяснение работы программы
- Пользователь вводит число, и оно сохраняется в переменную a .
- Инициализируем переменную k значением 0 . Эта переменная будет выполнять роль счетчика.
- Запускаем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении). Напоминаем, что само число и 1 делителями мы считать не будем.
- Затем, при помощи инструкции if , на каждой итерации цикла мы проверяем, делится ли наше число без остатка на числа из выбранного диапазона цикла. Если делится, то переменная k , выполняющая роль счетчика, увеличивается на единицу.
- Если число делителей равно 0 , то проверяемое число является простым.
- Выводим полученный результат на экран.
Результаты работы программы
Пример 1: Введите число: 7 Число простое Пример 2: Введите число: 35 Число не является простым
Еще более 50 задач на числа в нашем телеграм канале Python Turbo. Уютное сообщество Python разработчиков.
Источник: pythonist.ru
Решение модуля 4.4 Инди-курс программирования на Python
Ниже представлены примеры задач с решением на тему Нахождение всех делителей числа.
Какова сумма всех натуральных делителей числа 34?
Дано натуральное число N. Определить, является ли оно простым. Натуральное число N называется простым, если у него есть только два делителя: единица и само число N.
В качестве ответа выведите «Yes», если число простое, «No» — в противном случае.
n = int(input()) i = 1 a = [] # список делителей числа n while i ** 2
Программа получает на вход натуральное число N.
Нужно найти сумму его делителей.
n = int(input()) c = 1 sum=0 while c
Источник: zazloo.ru