🔍 Как сгенерировать простое число в Python?

  
  def is_prime(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 generate_prime():
      num = 2
      while True:
          if is_prime(num):
              return num
          num += 1
  
  prime_number = generate_prime()
  print(prime_number)
  
  

Как сгенерировать простое число в Python?

Генерация простых чисел является важной задачей в программировании. Простые числа - это числа, которые могут быть делены только на 1 и на само себя без остатка. В этой статье мы рассмотрим несколько методов генерации простых чисел с использованием Python.

Метод 1: Перебор делителей

Простым, но не самым эффективным способом генерации простых чисел является перебор делителей. Мы будем перебирать числа, начиная с 2, и проверять, делится ли число на какое-либо другое число без остатка. Если число не делится ни на одно число, кроме 1 и самого себя, то оно будет простым числом.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_prime_numbers(n):
    primes = []
    num = 2
    while len(primes) < n:
        if is_prime(num):
            primes.append(num)
        num += 1
    return primes

# Пример использования:
prime_numbers = generate_prime_numbers(10)
print(prime_numbers)
    

Этот код включает функцию `is_prime(n)`, которая проверяет, является ли число `n` простым, и функцию `generate_prime_numbers(n)`, которая генерирует список первых `n` простых чисел. В примере мы генерируем список первых 10 простых чисел и выводим его.

Метод 2: Решето Эратосфена

Решето Эратосфена - это алгоритм, который позволяет нам найти все простые числа до определенного числа `n`. Он основан на предположении, что все числа, делящиеся на простые числа, также не являются простыми.

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    primes = []
    
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False
    
    for i in range(2, n + 1):
        if sieve[i]:
            primes.append(i)
    
    return primes

# Пример использования:
prime_numbers = sieve_of_eratosthenes(100)
print(prime_numbers)
    

В этом коде мы определяем функцию `sieve_of_eratosthenes(n)`, которая использует решето Эратосфена для нахождения всех простых чисел до `n`. Мы применяем фильтрацию через решето, и на выходе получаем список всех простых чисел до указанного числа `n`. В примере мы находим все простые числа до 100 и выводим их.

Заключение

Теперь вы знаете два метода генерации простых чисел в Python: перебор делителей и решето Эратосфена. Используйте эти методы в своих кодах, когда вам потребуется работать с простыми числами. Оба метода имеют свои преимущества и ограничения, и их выбор зависит от вашего конкретного использования.