Số nguyên đặc biệt là một số nguyên dương chỉ có đúng 3 ước số nguyên dương. Đếm số lượng số nguyên đặc biệt trong đoạn từ 1 đến n. input: Một dòng số nguyên n (1<=n<10 ) output: Ghi ra gồm 1 dòng là kết quả tìm được. Ví dụ input output 5 1

Thuật toán: Số nguyên dương có đúng 3 ước là bình phương của 1 số nguyên tố. Vậy ta chỉ cần duyệt i từ 2 đến `sqrt(n)` . Nếu i là số nguyên tố ta tăng biến điếm lên 1.

#include <bits/stdc++.h>

using namespace std;

bool check(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    long long n,dem=0;
    cin>>n;
    for(int i=2;i*i<=n;i++)
    {
        if(check(i)) dem++;
    }
    cout<<dem;
}

Giải thích các bước giải:

#include <bits/stdc++.h>
#include <vector>
#define ll long long
using namespace std;
bool check(ll n)
{
    if (n < 2)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main()
{
    ll n,cnt=0;
    cin>>n;
    for(int i=2;i*i<=n;i++)
    {
        if(check(i)) 
            cnt++;
    }
    cout<<cnt;
}