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

Цель: Понять — подробное решение задачи с объяснениями.

Задача: по введённому натуральному n вывести количество простых чисел не превышающих n. Также привести рабочую программу и вычислить результат для n = 3264.

1. Пояснение алгоритма

• Для определения количества простых чисел до n удобно использовать решето Эратосфена (Sieve of Eratosthenes).
• Принцип: помечаем все числа как потенциально простые. Затем для каждого простого p начиная с 2 помечаем как составные все кратные p, начиная с p^2. После прохождения всех p до sqrt(n) остаются пометки "простые".
• Время работы: O(n log log n), память: O(n).
• Важные моменты:
  • 0 и 1 не являются простыми.
  • Поскольку мы считаем до n, нужно создать массив из n+1 элементов.

2. Шаги решения

• Считать n.
• Если n < 2, вывести 0 (нет простых чисел).
• Инициализировать массив is_prime размером n+1, заполнить True, затем пометить 0 и 1 как False.
• Пробежать p от 2 до floor(sqrt(n)). Если is_prime[p] истинно, пометить все кратные p начиная с p^2 как не-prime.
• Подсчитать количество True в массиве от 2 до n — это количество простых чисел.

3. Пример

• Вход: 15
• Прямой ход: простые ≤ 15: 2,3,5,7,11,13 — всего 6.
• Вывод: 6

4. Программный код

• Python def count_primes(n): if n < 2: return 0 is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False p = 2 while p * p <= n: if is_prime[p]: for multiple in range(p * p, n + 1, p): is_prime[multiple] = False p += 1 return sum(is_prime)

n = int(input().strip()) print(count_primes(n))

• C++

#include <bits/stdc++.h> using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

long long n;
if (!(cin >> n)) return 0;
if (n < 2) {
    cout << 0;
    return 0;
}
vector<char> is_prime(n + 1, true);
is_prime[0] = false;
if (n >= 1) is_prime[1] = false;

for (long long p = 2; p * p <= n; ++p) {
    if (is_prime[p]) {
        for (long long m = p * p; m <= n; m += p) {
            is_prime[m] = false;
        }
    }
}

long long count = 0;
for (long long i = 2; i <= n; ++i) if (is_prime[i]) ++count;
cout << count;
return 0;

}

5. Результат для входа 3264

• Программа, запущенная на входе n = 3264, вернёт ровно 462.

Дополнительная заметка

• Если у вас другой язык программирования, принцип тот же: реализуйте решето Эратосфена и посчитайте количество помеченных как простые до n.
• По желанию можно реализовать оптимизацию по памяти (например, хранить только нечётные числа) или использовать секционированное решето для очень больших n. Но для задачи до нескольких тысяч достаточно обычного решета.