10001-е простое число
Добро пожаловать в очередную статью, посвященную решению задач проекта Эйлера! Сегодня мы разберем задачу №7, где нужно найти 10001-е простое число.
Описание задачи:
Перечислив первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число - 13.
Каково 10001-е простое число?
Для решения этой задачи мы рассмотрим два подхода:
- Проверка на простоту делением: Этот метод проверяет, делится ли число на какое-либо из чисел от 2 до его квадратного корня. Если нет, то число является простым.
- Решето Эратосфена: Этот метод создает список всех чисел до заданного предела и затем последовательно вычеркивает все кратные каждому простому числу. Оставшиеся числа будут простыми.
Решение 1: Проверка на простоту делением
def is_prime(n):
"""Проверяет, является ли число n простым."""
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
def find_nth_prime(n):
"""Находит n-е простое число."""
count, number = 0, 2
while count < n:
if is_prime(number):
count += 1
number += 1
return number - 1
# Находим 10001-е простое число
nth_prime = find_nth_prime(10001)
print(f"10001-е простое число: {nth_prime}")
10001-е простое число: 104743
Решение 2: Решето Эратосфена
def sieve_of_eratosthenes(n):
"""Находит все простые числа до n с помощью решета Эратосфена."""
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 [i for i, is_prime in enumerate(primes) if is_prime]
# Находим 10001-е простое число
primes = sieve_of_eratosthenes(150000) # Достаточно большой предел для поиска
nth_prime = primes[10000] # Индексация с 0
print(f"10001-е простое число: {nth_prime}")
10001-е простое число: 104743
Сравнение методов
Проверка на простоту делением является простым для понимания и реализации методом. Он последовательно проверяет делимость числа на все числа от 2 до его квадратного корня. Однако, этот метод становится неэффективным для больших чисел, так как количество проверок растет.
Решето Эратосфена - более эффективный метод для поиска множества простых чисел. Он создает список всех чисел до заданного предела и затем вычеркивает все кратные каждому простому числу. Оставшиеся числа являются простыми. Однако, этот метод требует больше памяти, чем проверка на простоту делением.
Заключение
Мы рассмотрели два метода решения 7-й задачи Эйлера. Выбор метода зависит от конкретной задачи. Если нужно найти одно конкретное простое число, то проверка на простоту может быть достаточной. Если же нужно найти множество простых чисел, то решето Эратосфена будет более эффективным.
Надеюсь, эта статья была вам полезна! Не стесняйтесь оставлять комментарии и делиться своими мыслями.
ИИ так решил.
Комментариев нет:
Отправить комментарий