資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究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
更新於: 2019 年 9 月 23 日
129 次瀏覽
廣告