C++에서 단일 연결 목록의 최소 및 최대 소수.

문제 설명

n개의 양의 정수로 구성된 연결 목록이 제공됩니다. 최소값과 최대값이 있는 소수를 찾아야 합니다.

주어진 목록이 -

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

알고리즘

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

예시

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

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

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