Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên tố trong một mảng gồm n số nguyên dương. Các số nguyên tố này phải thỏa mãn điều kiện giá trị của chúng nhỏ hơn một giá trị cho trước k. Đầu vào bao gồm hai số nguyên n và k, tiếp theo là n số nguyên dương của mảng. Đầu ra là số lượng các số nguyên tố trong mảng có giá trị nhỏ hơn k.

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

Cách Kiểm tra nguyên tố riêng lẻ (Sàng Eratosthenes)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("bai2.inp","r",stdin);
    freopen("bai2.out","w",stdout);
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int i=0;i<n;++i)cin>>a[i];
    vector<bool>check(k+1,true);
    check[0]=false;check[1]=false;
    for(int i=2;i<=k;++i) if (check[i]) for(int j=i*i;j<=k;j+=i)check[j]=false;
    int ans=0;
    for(int i:a) if (i<k&&check[i]) ans++;
    cout<<ans;
    return 0;
}

• Time Complexity: O((k log log k) + n)
• Space Complexity: O(k)

Phương pháp này sử dụng thuật toán sàng Eratosthenes để tạo ra một mảng đánh dấu (mảng check) các số nguyên tố từ 1 đến k. Mảng check cho phép kiểm tra xem một số bất kỳ có phải là số nguyên tố hay không trong thời gian O(1).

1. Tạo mảng check có kích thước k+1, khởi tạo tất cả giá trị là true.
2. Đánh dấu check[0] và check[1] là false (vì 0 và 1 không phải số nguyên tố).
3. Duyệt từ i = 2 đến k. Nếu check[i] là true (tức i là số nguyên tố), duyệt đánh dấu tất cả các bội số của i (ii, ii+i, ...) là false.
4. Sau khi sàng, duyệt mảng a, với mỗi phần tử x, nếu x < k và check[x] là true thì tăng biến đếm.

Độ phức tạp thời gian: O(k log log k) để sàng + O(n) để duyệt mảng đầu vào. Độ phức tạp không gian: O(k) cho mảng check.

Cách Kiểm tra nguyên tố riêng lẻ (Vòng lặp tối ưu)

#include<bits/stdc++.h>
using namespace std;
bool ngto(long n)
{
    if(n==1)
    {
        return false;
    }
    if(n==2 or n==3)
    {
        return true;
    }
    if(n%2==0 or n%3==0)
    {
        return false;
    }
    for(long i=5;i*i<=n;i+=6)
    {
        if(n%i==0 or n%(i+2)==0)
            return false;
    }
    return true;
}
int main()
{
    long n,k,i,dem=0,a;
    freopen("bai2.inp","r",stdin);
    freopen("bai2.out","w",stdout);
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>a;
        if(a<k and ngto(a))
        {
            dem++;
        }
    }
    cout<<dem;
}

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

Phương pháp này kiểm tra tính nguyên tố của từng số trong mảng một cách độc lập. Hàm ngto sử dụng một số tối ưu hóa:

1. Xử lý các trường hợp cơ bản (n=1, 2, 3).
2. Kiểm tra chia hết cho 2 và 3 để loại bỏ nhanh các số chẵn và bội của 3.
3. Chỉ kiểm tra các ước số bắt đầu từ 5, tăng 6 đơn vị mỗi bước và kiểm tra cả i và i+2. Điều này dựa trên việc mọi số nguyên tố lớn hơn 3 đều có dạng 6k ± 1.

Độ phức tạp time: O(n * sqrt(V)), với V là giá trị lớn nhất của phần tử trong mảng. Space: O(1) do không cần mảng phụ.

Cách Kiểm tra nguyên tố cơ bản

#include<bits/stdc++.h>
#define ll long long
const ll N = 2e5+5;
using namespace std;
ll n, k;
ll prime(ll x) {
    if (x < 2) return 0;
    for (ll i=2; i<=sqrt(x); ++i) 
        if (x % i == 0) return 0;

    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    freopen("bai2.inp", "r", stdin);
    freopen("bai2.out", "w", stdout);

    cin >> n >> k;

    ll res = 0;

    for (ll i=1; i<=n; ++i) {
        ll x;
        cin >> x;

        if (prime(x) && x < k) ++res;
    }

    cout << res;

    return 0;
}

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

Đây là cách tiếp cận đơn giản nhất nhưng kém hiệu quả nhất trong các giải pháp được cung cấp. Nó kiểm tra tính nguyên tố của mỗi số bằng cách thử chia nó cho tất cả các số từ 2 đến căn bậc hai của nó.

Hàm prime:

1. Nếu x < 2, trả về 0 (không phải nguyên tố).
2. Duyệt i từ 2 đến sqrt(x). Nếu x chia hết cho i, trả về 0.
3. Nếu không tìm thấy ước nào, trả về 1.

Trong hàm main, với mỗi số x读取 được, nó gọi hàm prime và kiểm tra điều kiện x < k.

Độ phức tạp time: O(n * sqrt(V)), nhưng thường chậm hơn do không có tối ưu hóa so với phương pháp sàng hoặc kiểm tra tối ưu hóa 6k ± 1. Space: O(1).

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

Bài học kinh nghiệm

• Nếu tất cả các số trong mảng đều nhỏ hơn k, ta có thể dùng sàng Eratosthenes để tạo bảng tra cứu (lookup table) cho các số nguyên tố trước khi xử lý mảng, giúp việc kiểm tra trở nên c cực kỳ nhanh O(1).
• Đối với việc kiểm tra nguyên tố từng số riêng lẻ, có thể tối ưu hóa bằng cách chỉ kiểm tra các ước số lẻ và chỉ đến căn bậc hai của số đó.
• Nếu các số trong mảng có thể rất lớn (lớn hơn nhiều so với k), thì việc sàng Eratosthenes lên đến giá trị lớn nhất của mảng là không khả thi. Tuy nhiên, trong bài toán này, điều kiện 'nhỏ hơn k' gợi ý rằng ta chỉ cần quan tâm đến các số trong phạm vi [2, k-1], nên sàng Eratosthenes là lựa chọn tối ưu.

Lỗi thường gặp

• Quên kiểm tra điều kiện số đó phải nhỏ hơn k trước khi kiểm tra tính nguyên tố, dẫn đến việc tính toán không cần thiết cho các số lớn.
• Sử dụng biến kiểu int cho các số lớn (ví dụ: khi tính i*i trong vòng lặp sàng hoặc kiểm tra sqrt(x) có thể tràn số nếu x lớn, mặc dù trong bài này k có thể vừa phải nhưng nên chú ý đối với các bài toán tổng quát).
• Xử lý sai số 1 (không phải nguyên tố) và số 2 (là số nguyên tố chẵn duy nhất) trong hàm kiểm tra nguyên tố.