BÀI 2. SỐ ĐẶC BIỆT

Đức đang học về số học, cậu bé rất yêu thích những con số có tính chất đặc biệt. Số đặc biệt là số nguyên dương có đúng 3 ước nguyên dương. Với một số nguyên dương k cậu ấy muốn biết có bao nhiêu số đặc biệt trong các số 1,2,3,..,k.

Dữ liệu: Cho từ file văn bản SPNUM.INP một số nguyên  dương k (k ≤ 10¹²)

Kết quả: Ghi ra file văn bản SPNUM.OUT là kết quả của bài toán.

SPNUM.INP                        SPNUM.OUT

6                                              125

1                                                   5

2 TEST 

 

 

 

Giới hạn:

• Có 50% các test có k ≤ 10⁴
• Có 25% các test có k ≤ 10⁶
• Có 25% các test có k ≤ 10¹²

Ý tưởng: chỉ cần đếm xem từ 1 đến căn bậc hai của n có bao nhiêu số nguyên tố 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nmax = 1e5;
bool check (ll x)
{
    for (ll i = 2; i <= sqrt(x); ++i)
    if (x % i == 0) return false;
    return x > 1;
}
ll n, d = 0;
int main()
{
    freopen("spnum.inp" , "r" , stdin);
    freopen("spnum.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (ll i = 2; i <= sqrt(n); ++i)
    {
        if (check(i)) d++;
    }
    cout << d;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int k;
int dem(int n) {
    int d=0;
    for (int i=1;i<=sqrt(n);i++) {
        if (n%i==0) {
            d++;
            if (i!=n/i) {
                d++;
            }
        }
    }
    return d;
}

int main() {
    freopen("spnum.inp" , "r" , stdin);
    freopen("spnum.out" , "w" , stdout);
    cin>>k;
    int sdb=0;
    for (int i=1;i<=k;i++) {
        if (dem(i)==3) {
            sdb++;
        }
    }
    cout<<sdb;
    return 0;
}