Tóm tắt đề bài

Cho mảng \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(n \le 100\,000\), \(a_i \le 10^9\)). Hãy in ra các vị trí (chỉ số) của những phần tử là số nguyên tố theo thứ tự tăng dần. Nếu không có số nguyên tố nào thì in -1.

Phân tích

• \(n\) lớn tới \(100\,000\) nên cần xử lý tuyến tính theo \(n\).
• Giá trị \(a_i\) tới \(10^9\):
  • Không thể sàng nguyên tố tới \(10^9\).
  • Ta cần kiểm tra nguyên tố cho từng số bằng phép thử chia đến \(\sqrt{a_i}\).
• \(\sqrt{10^9} \approx 31623\), nên kiểm tra nguyên tố kiểu \(O(\sqrt{x})\) là khả thi:
  • Tối đa \(100\,000\) số, nhưng trung bình vẫn ổn trong giới hạn đề thi phổ thông, nhất là khi tối ưu (loại số chẵn, bước nhảy \(2\)).

Nhận xét quan trọng

• \(1\) không phải số nguyên tố.
• \(2\) là số nguyên tố chẵn duy nhất.
• Với \(x > 2\) mà chẵn thì chắc chắn không nguyên tố.

Hướng giải quyết

Ý tưởng

Duyệt mảng từ trái sang phải, với mỗi phần tử \(a_i\):

• Nếu \(a_i\) là số nguyên tố, in ra chỉ số \(i\).
• Cuối cùng nếu không in được chỉ số nào thì in -1.

Kiểm tra số nguyên tố

Hàm isPrime(x):

1. Nếu \(x < 2\) trả về false.
2. Nếu \(x = 2\) trả về true.
3. Nếu \(x\) chẵn trả về false.
4. Thử các ước lẻ \(d\) từ \(3\) đến khi \(d^2 > x\):
   • Nếu \(x \bmod d = 0\) thì không phải nguyên tố.
   • Nếu không có ước nào thì là nguyên tố.

Các lỗi thường gặp

• Quên loại trường hợp \(x = 1\).
• Dùng sqrt(x) kiểu số thực có thể gây sai số; an toàn hơn là dùng điều kiện \(d \cdot d \le x\) với kiểu long long.
• In dấu cách: nên gom các vị trí vào mảng rồi in một lần để tránh định dạng sai.

Độ phức tạp

• Thời gian: \(O\left(n \cdot \sqrt{\max(a_i)}\right)\) trong trường hợp xấu nhất, với \(\sqrt{10^9} \approx 31623\).
• Bộ nhớ: \(O(1)\) (hoặc \(O(k)\) nếu lưu danh sách vị trí nguyên tố, với \(k \le n\)).

Code tham khảo

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

static inline bool isPrime(long long x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (long long d = 3; d * d <= x; d += 2) {
        if (x % d == 0) return false;
    }
    return true;
}

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

    int n;
    cin >> n;
    vector<int> pos;
    pos.reserve(n);

    for (int i = 1; i <= n; i++) {
        long long a;
        cin >> a;
        if (isPrime(a)) pos.push_back(i);
    }

    if (pos.empty()) {
        cout << -1;
    } else {
        for (int i = 0; i < (int)pos.size(); i++) {
            if (i) cout << ' ';
            cout << pos[i];
        }
    }
    return 0;
}