数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告