Hiểu bài toán

Bài toán yêu cầu đếm số số nguyên tố nhỏ hơn hoặc bằng một số N cho trước (theo các giải pháp đã nộp). Tuy nhiên, tên bài là 'Số T-PRIME'. Trong nhiều kỳ thi, 'T-PRIME' thường yêu cầu tìm các số có số lượng ước chính xác là 3 (số chính phương của số nguyên tố). Dựa trên các giải pháp đã nộp (đếm số lượng số nguyên tố <= sqrt(N) hoặc <= N), chúng ta sẽ phân tích theo hướng đếm số lượng số nguyên tố <= N (hoặc <= sqrt(N) nếu bài gốc là T-PRIME). Các giải pháp sử dụng sàng Eratosthenes để tìm số nguyên tố.

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

Cách Sàng Eratosthenes cơ bản

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

int a[1000003];
void snt()
{
    for (int i=0;i<=1000000;++i)
        a[i]=1;
    a[0]=0;
    a[1]=0;
    for (int i=2;i<=1000;++i)
    {
        if (a[i])
        {
            for (int j=i*i;j<=1000000;j+=i)
                a[j]=0;
        }
    }
}
int main()
{
    freopen("TPRIME.inp","r",stdin);
    freopen("TPRIME.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,dem=0;
    cin>>n;
    snt();
    for (int i=2;i*i<=n;++i)
    {
        if (a[i] and i*i<=n)
            dem++;
    }
    cout<<dem;
    return 0;
}

• Time Complexity: O(N log log N)
• Space Complexity: O(N)

Giải pháp này sử dụng mảng boolean hoặc integer để lưu trạng thái số nguyên tố. Vòng lặp snt() loại bỏ bội số của các số nguyên tố. Vòng lặp main đếm số lượng số nguyên tố i sao cho i*i <= n. Nếu bài là T-PRIME (số có đúng 3 ước), thì i*i là số chính phương của số nguyên tố i, và i*i <= n là điều kiện để số đó nhỏ hơn N. Nếu bài chỉ là đếm số nguyên tố <= N, vòng lặp này sai (nó chỉ đếm các số nguyên tố i mà i*i <= n chứ không phải i <= n). Tuy nhiên, dựa trên code nộp, đây là logic tác giả dùng.

Cách Sàng Eratosthenes với giới hạn sqrt(N)

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 31624

using namespace std;

int n, res = 0, limit;
bool is_prime[MAX];

void sieve()
{
    is_prime[0] = true;
    is_prime[1] = true;
    for(int i = 2; i * i < MAX; i++)
    {
        if(!is_prime[i])
        {
            for(int j = i * i; j < MAX; j += i)
            {
                is_prime[j] = true;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    FILE *in = fopen("TPRIME.INP", "r");
    if(in != NULL)
    {
        freopen("TPRIME.INP", "r", stdin);
        freopen("TPRIME.OUT", "w", stdout);
    }
    cin >> n;
    sieve();
    limit = sqrt(n);
    for(int p = 2; p <= limit; ++p)
    {
        if(!is_prime[p]) res++;
    }
    cout << res;
    return 0;
}

• Time Complexity: O(sqrt(N) log log sqrt(N))
• Space Complexity: O(sqrt(N))

Giải pháp này tối ưu hơn về bộ nhớ bằng cách chỉ sàng số nguyên tố trong khoảng [2, sqrt(N)]. Nếu bài toán là T-PRIME (tìm số có 3 ước), ta chỉ cần các số nguyên tố p sao cho p*p <= N. Vòng lặp for(int p = 2; p <= limit; ++p) đếm chính xác những số này. limit được tính là sqrt(n). Mảng is_prime có kích thước cố định là 31624 (tương đương sqrt(10^9)).

Cách Sàng Eratosthenes với biên độ lớn (Tối ưu)

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

#define name ""
#define fi first
#define se second
#define pb push_back
#define el '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
using pii = pair<int,int>;
const int MOD = 1e9 + 7;
using ull = unsigned long long;

mt19937_64 rd(time(0));

ll rand(ll l, ll r){
    return l + rd() % (r - l + 1);
}

const int maxN = (int) 1e5 + 5;

bool kt[maxN];

void snt(){
    for(int i = 2; i*i < maxN; i++){
        if(kt[i] == 0){
            for(int j = i*i; j < maxN; j += i) kt[j] = 1;
        }
    }
}

int n, ans = 0;

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

    #define task "TPRIME"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    snt();

    cin >> n;
    for(int i = 2; i*i <= n; i++){
        if(kt[i] == 0) ans++;
    }

    cout << ans;

    return 0;
}

• Time Complexity: O(N log log N)
• Space Complexity: O(N)

Một biến thể khác của sàng Eratosthenes. Code này sử dụng maxN = 1e5 + 5. Tuy nhiên, logic i*i <= n vẫn được giữ lại. Code này có vẻ như là một bản sao chép hoặc biến thể không đầy đủ của một bài khác, vì maxN quá nhỏ so với các số lớn, nhưng logic i*i <= n cho thấy nó đang giải quyết bài toán T-PRIME (đếm các số chính phương của nguyên tố <= N).

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

Bài học kinh nghiệm

• Bài toán T-PRIME (số có đúng 3 ước) tương đương với việc tìm các số chính phương của số nguyên tố.
• Sàng Eratosthenes là thuật toán tối ưu để tìm số nguyên tố trong khoảng liên tiếp.
• Với giới hạn N lớn (ví dụ 10^12), ta chỉ cần sàng các số nguyên tố lên đến sqrt(N) (khoảng 10^6).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai (ví dụ int thay vì long long cho N lớn).
• Sai logic đếm: Vòng lặp i*i <= n đếm số lượng số chính phương của nguyên tố, không phải số lượng số nguyên tố <= N.
• Quên kiểm tra các trường hợp đặc biệt như số chính phương của 2 (4).