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.

Số có đúng 3 ước là bình phương số nguyên tố. Vậy ta chỉ cần đếm số lượng số nguyên tố trong đoạn `[1,sqrt(n)]`.

#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>
#define ll long long
using namespace std;
bool check(LL n)
{
    if (n<2)
        return false;
    for(ll i=2;i*i<=n;i++)
    {
        if (n%i==0)
            return false;
    }
    return true;
}

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