Số nguyên tố nhỏ nhất và lớn nhất trong danh sách liên kết đơn trong C++

Đề bài

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

Ví dụ: 10 → 4 → 1 → 12 → 13 → 7 → 6 → 2 → 27 → 33. Số nguyên tố min = 2, max = 13.

Thuật toán

1. Tìm số lớn nhất trong danh sách (maxNumber)
2. Sinh các số nguyên tố từ 1 đến maxNumber (sàng Eratosthenes), lưu vào mảng động
3. Duyệt linked list, dùng mảng nguyên tố để tìm min/max prime

Ví dụ mã C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <list>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void inMinMaxNguyenTo(list<int> intList){
    int maxNumber = *max_element(intList.begin(), intList.end());
    vector<bool> 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 (auto it = intList.begin(); it != intList.end(); ++it) {
        if (primes[*it]) {
            minPrime = min(minPrime, *it);
            maxPrime = max(maxPrime, *it);
        }
    }
    cout << "Số nguyên tố nhỏ nhất = " << minPrime << "\n";
    cout << "Số nguyên tố lớn nhất = " << maxPrime << "\n";
}

int main(){
    int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
    list<int> intList(arr, arr + SIZE(arr));
    inMinMaxNguyenTo(intList);
    return 0;
}

Kết quả đầu ra

Số nguyên tố nhỏ nhất = 2
Số nguyên tố lớn nhất = 13