資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中陣列中所有素數的乘積
給定一個包含一些元素的整數陣列 arr[]，任務是找到這些數字中所有素數的乘積。
素數是指只能被 1 或自身整除的數，或者說素數是一個除了 1 和自身之外不能被任何其他數整除的數。例如 1、2、3、5、7、11 等。
我們需要為給定的陣列找到解決方案 -
輸入 - arr[] = { 11, 20, 31, 4, 5, 6, 70 }
輸出 - 1705
說明 - 陣列中的素數為 - 11、31、5，它們的乘積為 1705
輸入 - arr[] = { 1, 2, 3, 4, 5, 6, 7 }
輸出 - 210
說明 - 陣列中的素數為 - 1、2、3、5、7，它們的乘積為 210
下面使用的解決問題的方法如下
獲取輸入陣列 arr[]。
迴圈每個元素並檢查它是否為素數。
將陣列中所有存在的素數相乘。
返回乘積。
演算法
Start
In function int prodprimearr(int arr[], int n)
Step 1→ Declare and initialize max_val as max_val *max_element(arr, arr + n)
Step 2→ Declare vector<bool> isprime(max_val + 1, true)
Step 3→ Set isprime[0] and isprime[1] as false
Step 4→ Loop For p = 2 and p * p <= max_val and p++
If isprime[p] == true then,
Loop For i = p * 2 and i <= max_val and i += p
Set isprime[i] as false
Step 5→ Set prod as 1
Step 6→ For i = 0 and i < n and i++
If isprime[arr[i]]
Set prod = prod * arr[i]
Step 6→ Return prod
In function int main(int argc, char const *argv[])
Step 1→ Declare and initilalize arr[] = { 11, 20, 31, 4, 5, 6, 70 }
Step 2→ Declare and initialize n = sizeof(arr) / sizeof(arr[0])
Step 3→ Print the results of prodprimearr(arr, n)
Stop示例
#include <bits/stdc++.h>
using namespace std;
int prodprimearr(int arr[], int n){
// To find the maximum value of an array
int max_val = *max_element(arr, arr + n);
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
vector<bool> isprime(max_val + 1, true);
isprime[0] = false;
isprime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// If isprime[p] is not changed, then
// it is a prime
if (isprime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
isprime[i] = false;
}
}
// Product all primes in arr[]
int prod = 1;
for (int i = 0; i < n; i++)
if (isprime[arr[i]])
prod *= arr[i];
return prod;
}
int main(int argc, char const *argv[]){
int arr[] = { 11, 20, 31, 4, 5, 6, 70 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << prodprimearr(arr, n);
return 0;
}輸出
如果執行以上程式碼，它將生成以下輸出 -
1705
更新於： 2020-08-13
184 次檢視
廣告