В этой задаче нам дано целое число n, и нам нужно найти количество почти простых чисел, меньших или равных n. Почти простое число определяется как натуральное число, имеющее ровно два различных простых делителя.

Чтобы решить эту проблему, нам сначала нужно сгенерировать все простые числа, меньшие или равные n, используя алгоритм решета Эратосфена. Решето Эратосфена — эффективный алгоритм нахождения всех простых чисел до заданного предела.

После создания всех простых чисел, меньших или равных n, мы можем перебрать все числа от 1 до n и подсчитать количество простых множителей. Мы можем сделать это, проверив, делится ли число на любое простое число, меньшее или равное его квадратному корню. Если оно делится ровно на два простых числа, то оно почти простое число.

Код сначала определяет логический массив prime размера N и инициализирует все значения истинными с помощью функции memset(). Затем он устанавливает значения с индексами 0 и 1 в false, поскольку они не являются простыми числами. Затем он перебирает все числа от 2 до квадратного корня из N и присваивает всем их кратным значение false в массиве prime.

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

В целом временная сложность алгоритма составляет O(nloglogn) из-за того, что алгоритм решета Эратосфена используется для генерации всех простых чисел, меньших или равных n.

Вот код:

// https://codeforces.com/group/yg7WhsFsAp/contest/355493/problem/P16
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 3001;
bool prime[N];

void sieve() {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i]) {
            for (int j = i * i; j < N; j += i) {
                prime[j] = false;
            }
        }
    }
}

int main() {
    sieve();
    int n;
    cin >> n;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int factors = 0;
        for (int j = 2; j <= i; j++) {
            if (prime[j] && i % j == 0) {
                factors++;
            }
        }
        if (factors == 2) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Если вы нашли эту статью полезной и информативной, не стесняйтесь подписываться на меня в моих учетных записях в социальных сетях, чтобы получать больше обновлений и информации о веб-разработке:

Спасибо, что нашли время прочитать эту статью. Желаю вам всего наилучшего в вашем учебном путешествии!