Chương trình C tìm số nguyên tố nhỏ nhất và lớn nhất trong mảng

Đề bài

Cho mảng n số nguyên dương. Tìm số nguyên tố có giá trị nhỏ nhất và lớn nhất.

Nếu mảng cho:

arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33}
thì số nguyên tố nhỏ nhất là 2 và lớn nhất là 13

Thuật toán

1. Tìm số lớn nhất trong mảng, gọi là maxNumber
2. Sinh các số nguyên tố từ 1 đến maxNumber lưu vào mảng động
3. Duyệt mảng đầu vào dùng mảng động tìm số nguyên tố min và max

Ví dụ

#include <iostream>
#include <vector>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
void printMinAndMaxPrimes(int *arr, int n) {
    int maxNumber = *max_element(arr, arr + n);
    vector primes(maxNumber + 1, true);
    primes[0] = primes[1] = false;
    for (int p = 2; p * p <= maxNumber; ++p) {
        if (primes[p]) {
            for (int i = p * 2; i <= maxNumber; i += p)
                primes[i] = false;
        }
    }
    int minPrime = INT_MAX;
    int maxPrime = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (primes[arr[i]]) {
            minPrime = min(minPrime, arr[i]);
            maxPrime = max(maxPrime, arr[i]);
        }
    }
    cout << "So nguyen to nho nhat = " << minPrime << "\n";
    cout << "So nguyen to lon nhat = " << maxPrime << "\n";
}
int main() {
    int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
    printMinAndMaxPrimes(arr, SIZE(arr));
    return 0;
}

Kết quả

Khi biên dịch và chạy chương trình, đầu ra:

So nguyen to nho nhat = 2
So nguyen to lon nhat = 13