题目描述
狮子座很爱学习，最近沉迷于研究素数，一天他发现了一个很神奇的数，叫做几乎素数。定义如下：如果一个数字恰好具有两个不同的素数除数，则称为几乎素数。 例如，数字6、18、24是几乎素数，而数字4、8、9、42不是。 请你帮忙找出介于1和n之间（含1和n）的几乎素数的数量。
输入
输入包含一个整数n（1≤n≤3000)
输出
输出1到n之间（含1和n）的几乎素数的数量。
样例输入 Copy
10
样例输出 Copy
2

思路：利用埃氏筛选素数思想，首先打表，素数不会被标记，每个素数的倍数都会被标记一次，所以按照题目的意思，我们只需要找到被标记两次的数，那么这个数就是几乎素数
埃氏筛应该是算是一种简单编写，容易理解的筛选素数的方法了
点我了解埃氏筛

#include <bits/stdc++.h>
using namespace std;
int num[3005];
int main()
{
   
    int n;
    for (int i = 2; i < 3005; ++i)
        if (!num[i])//如果没有标记过
        {
   
            for (int j = 2 * i; j < 3005; j += i)//如果是素数的倍数就标记一次
                num[j]++;
        }
    while (cin >> n)
    {
   
        int s = 0;
        for (int i = 2; i <= n; ++i)
            if (num[i] == 2)//如果有两个不同素数的因子
                s++;
        cout << s << endl;
    }
    return 0;
}
路漫漫其修远兮，吾将上下而求索。