Написать программу, которая находит все простые числа до числа [10^{123}].

Предмет: Информатика
Раздел: Алгоритмы и структуры данных, Теория чисел (в частности, работа с простыми числами), Высокоэффективные вычисления (Big Integer)

Задача:

Нужно написать программу, которая находит все простые числа до числа [10^{123}].

Важное замечание:

Число [10^{123}] — это огромное число, состоящее из 124 цифр. Хранить все простые числа до него невозможно даже на самых мощных суперкомпьютерах. Для оценки:

• Количество простых чисел до [N] можно примерно оценить по теореме о распределении простых чисел: \pi(N) \approx \frac{N}{\ln N}

Для [N = 10^{123}]: \pi(10^{123}) \approx \frac{10^{123}}{123 \cdot \ln 10} \approx \frac{10^{123}}{283}

Это примерно [3.53 \cdot 10^{120}] простых чисел — абсолютно нереальное количество для хранения или даже генерации.

Что можно сделать?

1. Невозможно сгенерировать все простые до [10^{123}].
2. Но можно написать программу, которая проверяет, является ли заданное число простым (например, до [10^{123}]).
3. Можно также написать генератор простых чисел, который будет перебирать числа и проверять их на простоту, не храня все найденные простые.

Решение: Проверка на простоту для больших чисел

Для больших чисел используется тест Миллера-Рабина — вероятностный тест на простоту. Он работает эффективно даже для чисел с сотнями цифр.

Пример программы: Проверка, является ли число простым (Python)

import random

def is_prime(n, k=10):
    """Проверка на простоту числа n с помощью теста Миллера-Рабина.
    k — количество раундов (чем больше, тем точнее)."""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # Представим n - 1 = 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        d //= 2
        r += 1

    # Повторить k раз
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)  # a^d mod n
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Составное
    return True  # Вероятно простое

# Пример использования:
number = int("1" + "0" * 122)  # 10^122
print(is_prime(number))

Альтернатива: Генератор простых чисел (до разумного предела)

Если всё же нужно генерировать простые числа, то это можно делать до разумного предела (например, [10^6] или [10^9]) с помощью решета Эратосфена:

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    return [i for i, prime in enumerate(is_prime) if prime]

# Пример:
primes = sieve(10**6)
print(primes[:10])  # Первые 10 простых чисел

Вывод:

• Сгенерировать все простые числа до [10^{123}] невозможно.
• Но можно написать программу, которая проверяет, является ли конкретное большое число простым (например, с помощью теста Миллера-Рабина).
• Также можно написать генератор простых чисел до разумного предела.

Если тебе нужно проверить конкретное число на простоту или сгенерировать простые до определённого значения — уточни, и я помогу!