Каким образом можно определить, является ли целое число простым с помощью алгоритма на языке программирования?
Каким образом можно определить, является ли целое число простым с помощью алгоритма на языке программирования?
Поделиться
Введите адрес электронной почты, который вы использовали при регистрации. Вы получите ссылку на сброс пароля
Напишите причину обращения
Существует несколько алгоритмов для определения простоты числа на языке программирования, но один из самых простых — это «Решето Эратосфена». Он работает следующим образом:
1. Создайте список чисел от 2 до проверяемого числа.
2. Начиная с числа 2, вычеркивайте все его кратные числа из списка.
3. Перейдите к следующему числу, которое еще не вычеркнуто, и повторите шаг 2.
4. Если проверяемое число осталось в списке, то оно простое, если нет — составное.
Пример реализации на Python:
«`
def is_prime(n):
if n < 2: return False primes = [True] * (n+1) primes[0] = primes[1] = False for i in range(2, int(n**0.5)+1): if primes[i]: for j in range(i*i, n+1, i): primes[j] = False return primes[n] ``` Эта функция использует решето Эратосфена для создания списка простых чисел и проверяет, присутствует ли проверяемое число в этом списке. Если да, то оно простое, иначе - составное.