• Ta duyệt các phần tử từ 1 tới n, nếu phần tử nào là số nguyên tố, thì ta cho bội của các số đó tăng thêm 1 giá trị.
• Sau khi duyệt xong, nếu phần tử nào có giá trị bằng 2 thì đó là số gần như nguyên tố (số cần tìm).
• Ta chỉ việc đếm những số gần như nguyên tố đó lại, rồi in đáp án ra là được

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    // 0- initialization
    int N=3000;
    vector <int> cntFactor(N+1,0);
    for(int i=2; i<=N; ++i){                // nếu để i*i<=N thì sẽ bỏ sót trường hợp nha
        if(cntFactor[i]==0){
            for(int j=i; j<=N; j+=i){       // nếu ai thấy giống sàng nguyên tố và để j=i*i để tối ưu code thì xem xét kĩ sẽ thiếu trường hợp nha: ví dụ số 101 và 2 là 2 số nguyên tố, nhân vào là 202, nhưng đếm từ số 2 thì cntFactor[202]=1, nhưng khi i=101, j=101*101=... nó vượt quá 202, và bỏ tót trường hợp, nên cho ra kết quả sai
                cntFactor[j]+=1;
            }
        }
    }

    // 1- input
    int k;
    cin >> k;

    // 2- process
    int ans=0;
    for(int i=0; i<=k; ++i){
        if(cntFactor[i]==2){
            ans++;
        }
    }

    // 3- output
    cout <<ans <<endl;





    return 0;
}

• Để kiểm tra một số có phải là số gần như nguyên tố hay không, ta chỉ việc đếm số nguyên nguyên tố của nó là được.
• Để làm việc trên, ta có thể làm như sau:
• Gọi số x là số ta kiểm tra xem số đó có phải số gần như nguyên tố hay không. Ta sẽ dùng 1 vòng for, duyệt từ 2 tới x (vì số nguyên tố bắt đầu từ 2). Tiếp đó ta kiểm tra nếu x%i==0 thì ta sẽ chia x cho i đến khi nào không chia được nữa thì thôi (làm như thế ta sẽ giảm được 1 số nguyên tố - trong tích cách thừa số nguyên tố tạo thành số đó), tiếp đó ta cộng giá trị đếm lên 1 đơn vị. Sau cùng, ta kiểm tra nếu giá trị đếm bằng 1 thì số đó là số nguyên tố, bằng 2 là số gần như nguyên tố, bằng 3, 4, 5 thì thuộc dạng bài khác (trong bài này ta chỉ quan tâm tới đếm bằng 2 thôi). Nếu đếm bằng 2 thì đáp án tăng lên 1.
• In đáp án ra màn hình nữa là xong
• Do đề bài input khá nhỏ chỉ có 3000 nên code đơn giản như thế này là được rồi

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

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

   int ans=0;
   for(int i=1; i<=k; ++i){
      int x=i;
      int cntFactor=0;

      for(int div=2; x>1; ++div){
         if(x%div==0){
            cntFactor+=1;

            for( ;x%div==0; ){
               x/=div;
            }
         }
      }

      if(cntFactor==2){
         ans+=1;
      }
   }

   cout <<ans <<endl;









   return 0;
}