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.从给定数字中找到最大数字。 让我们称之为maxNumber 2.生成从1到maxNumber的质数,并将它们存储在动态数组中 3.迭代链接列表,并使用动态数组查找具有最小值和最大值的素数
示例
#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