1. Идея

Нужно посчитать, сколько простых чисел находится среди чисел от 1 до n.

Простое число — это натуральное число больше 1, у которого ровно два делителя: 1 и оно само.

Самый прямой способ:

• перебрать все числа x от 2 до n;
• для каждого числа проверить, простое ли оно;
• если простое — увеличить ответ.

Проверку простоты делаем перебором делителей от 2 до квадратного корня из числа.

2. Наблюдения

Наблюдение 1

Число 1 не является простым, поэтому начинать перебор нужно с 2.

Наблюдение 2

Если число x составное, то у него есть делитель не больше, чем sqrt(x).

Почему это полезно: если проверять все делители до самого x - 1, это слишком долго. А вот если остановиться на моменте, когда d * d > x, то дальше проверять уже не нужно.

Например, для x = 35:

• 35 = 5 * 7,
• один из делителей обязательно не больше sqrt(35).

Значит, чтобы понять, простое число или нет, достаточно проверить делители 2, 3, 4, ..., пока d * d <= x.

Наблюдение 3

Если найден хотя бы один делитель, то число сразу составное, и дальше проверять не нужно.

3. Алгоритм

1. Считать n.
2. Завести переменную countPrimes = 0.
3. Для каждого числа x от 2 до n:
   • проверить, простое ли x:
     • если x < 2, то оно не простое;
     • перебрать d от 2, пока d * d <= x;
     • если x % d == 0, то число составное;
     • если делитель не найден, то число простое.
   • если x простое, увеличить countPrimes.
4. Вывести countPrimes.

4. Почему это работает

Докажем, что алгоритм действительно считает количество простых чисел от 1 до n.

Для каждого числа x алгоритм определяет, простое оно или нет.

• Если у x есть делитель d такой, что 2 <= d и d * d <= x, то x составное, и алгоритм это обнаружит.
• Если таких делителей нет, то у x вообще нет делителей, кроме 1 и самого x, значит оно простое.

Почему можно ограничиться только делителями до квадратного корня:

• если x = a * b и оба числа a и b были бы больше sqrt(x), то их произведение было бы больше x, что невозможно;
• значит, хотя бы один из делителей составного числа не превосходит sqrt(x).

Следовательно, проверка простоты работает верно для каждого x.

Дальше алгоритм перебирает все числа от 2 до n и увеличивает счётчик ровно для тех, которые простые. Значит, в конце в countPrimes будет точное количество простых чисел на отрезке от 1 до n.

5. Сложность

Пусть проверяется число x.

• Для него перебор делителей работает за O(sqrt(x)).
• Всего чисел от 2 до n примерно n.

Итоговая сложность:

• O(n * sqrt(n)) в худшем случае.

Память:

• O(1), так как используются только несколько переменных.

6. Код на C++17

#include <iostream>
using namespace std;

bool isPrime(int x) {
    if (x < 2) {
        return false;
    }
    for (int d = 2; 1LL * d * d <= x; d++) {
        if (x % d == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;

    int countPrimes = 0;
    for (int x = 2; x <= n; x++) {
        if (isPrime(x)) {
            countPrimes++;
        }
    }

    cout << countPrimes << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

count_primes = 0

for x in range(2, n + 1):
    is_prime = True
    d = 2
    while d * d <= x:
        if x % d == 0:
            is_prime = False
            break
        d += 1
    if is_prime:
        count_primes += 1

print(count_primes)