На вход с клавиатуры поступает натуральное число n, напишите программу, которая определит и выведет на экран количество простых натуральных чисел, которые не превышают n. Напишите программу для решения этой задачи и вычислите количество простых чисел при входном числе 3264.

Для решения задачи о нахождении количества простых натуральных чисел, которые не превышают заданное число \( n \), мы можем использовать алгоритм «Решето Эратосфена». Этот алгоритм позволяет эффективно находить все простые числа до указанного предела.

Вот пошаговая реализация программы на языке Python:

def count_primes(n):
    if n < 2:
        return 0
    sieve = [True] * (n + 1)  # Создаем список с True
    sieve[0], sieve[1] = False, False  # 0 и 1 не простые числа

    for start in range(2, int(n**0.5) + 1):  # Проверяем числа до √n
        if sieve[start]:  # Если число простое
            for multiple in range(start*start, n + 1, start):
                sieve[multiple] = False  # Помечаем кратные как составные

    return sum(sieve)  # Считаем количество простых чисел

n = 3264
prime_count = count_primes(n)
print(f"Количество простых чисел не превышающих {n}: {prime_count}")

Как работает программа:

1. Инициализация списка: Создаётся список sieve длиной \( n+1 \) (где индекс соответствует числу), изначально заполняем его значениями True.
2. Обозначение не простых чисел: Поскольку 0 и 1 не являются простыми, мы устанавливаем для них значения False.
3. Основной цикл: Мы перебираем числа от 2 до квадратного корня из \( n \). Если текущее число start является простым (то есть sieve[start] равно True), то мы помечаем все его кратные как составные (устанавливаем False).
4. Подсчёт простых чисел: В конечном итоге, количество простых чисел будет равно количеству True значений в списке sieve.

Результат:

При выполнении данной программы для \( n = 3264 \), она подсчитает и выведет количество простых чисел, которые не превышают это значение. Вы можете запустить этот код в своем Python окружении для получения результата.

Если вас интересуют дополнительные детали или другие алгоритмы, не hesitate to ask!