Hiểu bài toán

Một số nguyên tố đặc biệt được định nghĩa là số nguyên dương chỉ có đúng 3 ước số nguyên dương. Yêu cầu đếm số lượng các số nguyên tố đặc biệt này trong đoạn từ 1 đến n (n có thể lên tới 10^9).

Các cách tiếp cận

Cách Brute Force (Kiểm tra từng số)

#include <iostream>
#include <cmath>
using namespace std;

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

int main() {
    long long n;
    cin >> n;

    int count = 0;
    long long limit = sqrt(n);

    for (int i = 2; i <= limit; i++) {
        if (isPrime(i)) count++;
    }

    cout << count;
}

• Time Complexity: O(sqrt(n) * sqrt(sqrt(n)))
• Space Complexity: O(1)

Phương pháp này dựa trên nhận định: Một số có đúng 3 ước số thì phải là lũy thừa của một số nguyên tố p^2 (các ước là 1, p, p^2). Nếu n có dạng p^2, thì p phải là số nguyên tố và p <= sqrt(n). Do đó, bài toán quy về đếm số lượng số nguyên tố trong khoảng [2, sqrt(n)]. Code trên sử dụng vòng lặp từ 2 đến sqrt(n), với mỗi số i kiểm tra tính nguyên tố bằng cách lặp từ 2 đến sqrt(i).

Cách Sàng Eratosthenes (Optimized)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    cin >> N;
    long long limit = sqrt(N);
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (long long i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= limit; j += i)
                isPrime[j] = false;
        }
    }

    int count = 0;
    for (int i = 2; i <= limit; i++)
        if (isPrime[i]) count++;

    cout << count;
    return 0;
}

• Time Complexity: O(sqrt(n) * log(log(sqrt(n))))
• Space Complexity: O(sqrt(n))

Đây là cách tối ưu hóa của phương pháp 1. Thay vì kiểm tra tính nguyên tố cho từng số một cách độc lập, ta sử dụng thuật toán sàng Eratosthenes để tạo ra một mảng đánh dấu các số nguyên tố trong khoảng [2, sqrt(n)]. Việc này giúp giảm thời gian chạy đáng kể so với việc kiểm tra lặp lại các thừa số. Độ phức tạp thời gian tổng thể là O(sqrt(n) log log sqrt(n)).

Cách Sử dụng hàm sqrt chuẩn xác

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    if(!(cin >> N)) return 0;
    long long m = floor(sqrt((long double)N));
    if(m < 2) { cout << 0 << '\n'; return 0; }
    int limit = (int)m;
    vector<char> is_prime(limit+1, true);
    is_prime[0] = is_prime[1] = false;
    for(int p = 2; (long long)p * p <= limit; ++p) {
        if(is_prime[p]) {
            for(int q = p*p; q <= limit; q += p) is_prime[q] = false;
        }
    }
    int cnt = 0;
    for(int i = 2; i <= limit; ++i) if(is_prime[i]) ++cnt;
    cout << cnt << '\n';
    return 0;
}

• Time Complexity: O(sqrt(n) * log(log(sqrt(n))))
• Space Complexity: O(sqrt(n))

Đây là biến thể của phương pháp sàng Eratosthenes. Điểm khác biệt chính nằm ở cách tính giới hạn limit. Thay vì dùng phép chia 2 nguyên (nếu dùng int n), code này dùng sqrt((long double)N) để đảm bảo độ chính xác cao cho số n lớn. Sau đó dùng floor để lấy giá trị nguyên. Logic sàng và đếm số nguyên tố vẫn giữ nguyên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Một số có đúng 3 ước số nguyên dương khi và chỉ khi nó là bình phương của một số nguyên tố (p^2).
• Vấn đề được giảm độ phức tạp từ việc tìm các số 'đặc biệt' trực tiếp sang việc đếm số lượng số nguyên tố trong khoảng [2, sqrt(n)].

Lỗi thường gặp

• Làm tròn sai hàm sqrt đối với các số lớn, dẫn đến sai lệch giới hạn sàng (dùng static_cast hoặc floor để tránh lỗi số thực).
• Xử lý sai trường hợp n < 4 (khi đó sqrt(n) < 2, không có số nguyên tố đặc biệt).
• Quên tối ưu hóa vòng lặp sàng (dùng i*i và j=j+i).