Minimum and Maximum Prime Numbers of a Singly Linked List in C++.

Problem statement

Given a linked list of n positive integers. We have to find the prime number with minimum and maximum value.

If the given list is −

10 -> 4 -> 1 -> 12 -> 13 -> 7 -> 6 -> 2 -> 27 -> 33 then minimum prime number is 2 and maximum prime number is 13

Algorithm

1. Find maximum number from given number. Let us call it maxNumber 2. Generate prime numbers from 1 to maxNumber and store them in a dynamic array 3. Iterate linked list and use dynamic array to find prime number with minimum and maximum value

Example

#include <iostream> #include <vector> #include <climits> #include <algorithm> #include <list> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; void printMinAndMaxPrimes(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 << "Prime number of min value = " << minPrime << "\n";    cout << "Prime number of max value = " << maxPrime << "\n"; } int main(){    int arr [] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};    list<int> intList(arr, arr + SIZE(arr));    printMinAndMaxPrimes(intList);    return 0; }

Output

When you compile and execute the above program. It generates the following output −

Prime number of min value = 2 Prime number of max value = 13