题解 | 几乎是质数

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<int> primeNumbers;

void generatePrime(int a)
{
    for (int i=2; i<=a/2; i++)
    { 
        bool flag = true;
        for (int j=2; j<i; j++)
        {
            if (i%j==0)
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            // cout << i << endl;
            primeNumbers.emplace_back(i);
        }
    }
    return;
}


bool isPrime(int a)
{
    bool hit = false;
    int count = 0;
    int n = primeNumbers.size();
     for (int i=0; i<n;)
     {  
        if (a%primeNumbers[i] == 0)
        {
            a = a/primeNumbers[i];
            hit = true;
            continue;
        }
        
        if (hit) count++;
        hit = false;
        i++;
     }
     if (count == 2) return true;
     return false;
}






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

    generatePrime(a);
    // cout << primeNumbers.size() << endl;

    int count = 0;
    for (int i=6; i<=a; i++)
    {
        if(isPrime(i)) count++;
    }

     cout << count << endl;
    

}
// 64 位输出请用 printf("%lld")