Hiểu bài toán

Cho một mảng gồm n số nguyên. Nhiệm vụ là tìm và in ra các số nguyên tố có trong mảng. Yêu cầu:

• In ra theo thứ tự tăng dần.
• Chỉ in ra 1 lần duy nhất cho mỗi số nguyên tố, ngay cả khi nó xuất hiện nhiều lần trong mảng.
• Các số cách nhau bởi một dấu cách.

Constraints:

• n <= 10,000.
• Giá trị tuyệt đối của các phần tử <= 1000.

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

Cách Brute Force với Kiểm tra Nguyên tố Từng số (Có Lặp)

#include <stdio.h>
#include <math.h>

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

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // Sắp xếp mảng để nhóm các số giống nhau và tăng dần
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }

    int lastPrinted = -1; // Biến để theo dõi số đã in
    for (int i = 0; i < n; i++) {
        // Chỉ in nếu là số nguyên tố và chưa in số này trước đó
        if (a[i] != lastPrinted && isPrime(a[i])) {
            printf("%d ", a[i]);
            lastPrinted = a[i];
        }
    }
    return 0;
}

• Time Complexity: O(n^2) hoặc O(n log n) tùy vào thuật toán sắp xếp
• Space Complexity: O(1)

Cách tiếp cận này không sử dụng bộ nhớ đệm quá nhiều.

1. Sắp xếp mảng: Sử dụng thuật toán sắp xếp đơn giản (như Bubble Sort) hoặc built-in sort để các phần tử giống nhau đứng cạnh nhau và mảng tăng dần.
2. Duyệt và Loại bỏ Trùng lặp: Duyệt qua mảng đã sắp xếp. Sử dụng một biến lastPrinted để lưu giá trị vừa in. Nếu phần tử hiện tại khác lastPrinted và là số nguyên tố, ta in nó ra và cập nhật lastPrinted.

Ưu điểm: Logic đơn giản, dễ hiểu. Nhược điểm: Sắp xếp tốn O(n log n) nếu dùng hiệu quả, hoặc O(n^2) nếu tự viết. Việc kiểm tra nguyên tố lặp lại cho các số giống nhau là lãng phí.

Cách Sử dụng Mảng Đếm (Counting Array)

#include <stdio.h>
#include <stdbool.h>

// Hàm kiểm tra nguyên tố
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() {
    int n;
    scanf("%d", &n);

    // Mảng đếm với kích thước đủ chứa giá trị lớn nhất (1000)
    // Ta cần offset nhỏ nhất (-1000) nên khai báo lớn hơn
    int count[2005] = {0}; 

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        // Kiểm tra âm hoặc dương và đánh dấu
        // Ví dụ: val = -5 -> index = -5 + 1000 = 995
        if (val >= -1000 && val <= 1000)
            count[val + 1000] = 1; 
    }

    int first = 1;
    for (int i = 0; i <= 2000; i++) {
        if (count[i] == 1) {
            int num = i - 1000; // Trả về số gốc
            if (isPrime(num)) {
                if (!first) printf(" ");
                printf("%d", num);
                first = 0;
            }
        }
    }
    return 0;
}

• Time Complexity: O(V) với V là khoảng giá trị (khoảng 2000)
• Space Complexity: O(V)

Phương pháp này sử dụng một mảng count để đánh dấu sự tồn tại của các số.

1. Khởi tạo mảng đếm: Do giá trị nằm trong khoảng [-1000, 1000], ta có thể dùng mảng kích thước ~2005.
2. Đánh dấu sự tồn tại: Đọc từng số, ta đánh dấu vị trí tương ứng trong mảng đếm. Ví dụ: số 5 được đánh dấu tại index 5+1000.
3. Kiểm tra và In: Duyệt qua mảng đếm từ đầu đến cuối. Nếu một vị trí được đánh dấu, ta lấy lại số gốc và kiểm tra xem nó có phải là số nguyên tố không. Vì ta duyệt theo thứ tự tăng dần của chỉ số, thứ tự in ra sẽ tự động tăng dần. Do mỗi số chỉ được đánh dấu 1 lần, nó chỉ được in 1 lần.

Ưu điểm: Rất nhanh, loại bỏ được hoàn toàn việc lặp lại và cần sắp xếp. Độ phức tạp phụ thuộc vào khoảng giá trị, không phụ thuộc nhiều vào n.

Cách Tối ưu với Sieve of Eratosthenes (Sàng Nguyên Tố)

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define MAX 1001
bool is_prime[MAX];
bool present[MAX]; // Mảng đánh dấu sự xuất hiện

void sieve() {
    // Khởi tạo tất cả là true
    for (int i = 0; i < MAX; i++) {
        is_prime[i] = true;
        present[i] = false;
    }
    is_prime[0] = is_prime[1] = false;

    // Sàng nguyên tố
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    sieve();

    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        // Chỉ quan tâm số dương và trong phạm vi sàng
        if (x > 0 && x < MAX) {
            if (is_prime[x]) {
                present[x] = true;
            }
        }
    }

    // In ra các số đã được đánh dấu là nguyên tố và xuất hiện
    int first = 1;
    for (int i = 2; i < MAX; i++) {
        if (present[i]) {
            if (!first) printf(" ");
            printf("%d", i);
            first = 0;
        }
    }

    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất cho các bài toán với giới hạn giá trị nhỏ (<= 1000).

1. Sàng Nguyên Tố (Sieve): Ta precompute (tính trước) tất cả các số nguyên tố trong phạm vi [1, 1000] bằng thuật toán Sieve of Eratosthenes. Quá trình này rất nhanh.
2. Kiểm tra Mảng: Khi đọc dữ liệu vào, ta chỉ cần kiểm tra xem số đó có phải là số nguyên tố đã được tính sẵn trong mảng is_prime không. Nếu có, ta đánh dấu nó trong một mảng present.
3. In kết quả: Duyệt từ 2 đến 1000, nếu số nào được đánh dấu trong present thì in ra.

Ưu điểm: Tốc độ cực nhanh, Logic gọn gàng, tách biệt việc kiểm tra nguyên tố ra khỏi việc xử lý mảng đầu vào.

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

Bài học kinh nghiệm

• Vì giới hạn giá trị đầu vào nhỏ (|A_i| <= 1000), ta có thể tối ưu hóa bằng cách tính toán trước các số nguyên tố (Sàng Eratosthenes) hoặc sử dụng mảng đếm thay vì kiểm tra từng số một cách lặp lại.
• Bài toán yêu cầu loại bỏ trùng lặp và sắp xếp tăng dần. Sử dụng mảng đếm hoặc duyệt theo chỉ số tăng dần của mảng đánh dấu là cách hiệu quả nhất để đạt được yêu cầu này mà không cần sắp xếp thủ công.
• Mảng count hoặc present có thể được offset (dịch chỉ số) để xử lý các số âm, hoặc có thể chỉ cần mảng boolean cho các số dương.

Lỗi thường gặp

• Quên xử lý số âm hoặc số 1 (số 1 không phải là số nguyên tố).
• In thừa dấu cách ở cuối cùng (cần kiểm soát việc in dấu cách, ví dụ chỉ in dấu cách trước các phần tử sau phần tử đầu tiên).
• Quên khai báo mảng đủ lớn để chứa các giá trị (ví dụ mảng 1001 thay vì 1000).
• Trong giải pháp sàng nguyên tố, cần đảm bảo sàng đúng phạm vi (ví dụ i * i < MAX thay vì i < MAX).