เลขเฉพาะค่าต่ำสุดและสูงสุดใน Singly Linked List ใน C++

Problem statement

ให้ Linked List ของ n จำนวนเต็มบวก เราต้องหาเลขเฉพาะที่มีค่าน้อยที่สุดและมากที่สุด

ถ้ารายการคือ −

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

อัลกอริทึม

1. หาตัวเลขสูงสุดจากรายการ เรียกว่า maxNumber 2. สร้างเลขเฉพาะจาก 1 ถึง maxNumber เก็บใน dynamic array 3. วนลูป linked list และใช้ dynamic array หาเลขเฉพาะค่าต่ำสุดและสูงสุด

ตัวอย่าง

#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; }

ผลลัพธ์

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