C ++数组中每个第K个素数的乘积

  • Z时代
  • 2024-01-10
  • 分类：综合

给定一个包含n个质数和k的数组arr [n]；任务是找到数组中第k个素数的乘积。

像，我们有一个数组arr [] = {3，5，7，11}并且k = 2，所以每k之后的质数，即5和11，我们必须找到它们的乘积将为5x11 = 55并打印结果作为输出。

什么是质数？

质数是自然数，除以1或数字本身不能除以任何其他数。一些质数是2、3、5、7、11、13等。

示例

Input: arr[] = {3, 5, 7, 11, 13} k= 2
Output: 55
Explanation: every 2nd element of the array are 5 and 11; their product will be 55
Input: arr[] = {5, 7, 13, 23, 31} k = 3
Output: 13
Explanation: every 3rd element of an array is 13 so the output will be 13.

我们将用来解决上述问题的方法-

  • 取n个元素和k的输入数组，以查找第k个元素的乘积。

  • 创建一个用于存储质数的筛子。

  • 然后，我们必须遍历数组并获取第k个元素，然后对每个第k个元素将其与乘积变量递归相乘。

  • 打印产品。

算法

Start
Step 1-> Define and initialize MAX 1000000
Step 2-> Define bool prime[MAX + 1]
Step 3-> In function createsieve()   Call memset(prime, true, sizeof(prime));
   Set prime[1] = false
   Set prime[0] = false
   Loop For p = 2 and p * p <= MAX and p++
      If prime[p] == true then,
         For i = p * 2 and i <= MAX and i += p
         Set prime[i] = false
Step 4-> void productOfKthPrimes(int arr[], int n, int k)
   Set c = 0
   Set product = 1
   Loop For i = 0 and i < n and i++
   If prime[arr[i]] then,
      Increment c by 1
      If c % k == 0 {
         Set product = product * arr[i]
         Set c = 0
      Print the product
Step 5-> In function main()   Call function createsieve()   Set n = 5, k = 2
   Set arr[n] = { 2, 3, 11, 13, 23 }
   Call productOfKthPrimes(arr, n, k)
Stop

示例

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void createsieve() {
   memset(prime, true, sizeof(prime));
   //0和1不是质数
   prime[1] = false;
   prime[0] = false;
   for (int p = 2; p * p <= MAX; p++) {
      if (prime[p] == true) {
         //求p的所有倍数
         for (int i = p * 2; i <= MAX; i += p)
         prime[i] = false;
      }
   }
}
//计算答案
void productOfKthPrimes(int arr[], int n, int k) {
   //计算素数
   int c = 0;
   //查找素数的乘积
   long long int product = 1;
   //遍历数组
   for (int i = 0; i < n; i++) {
      //如果数字是素数
      if (prime[arr[i]]) {
         c++;
         if (c % k == 0) {
            product *= arr[i];
            c = 0;
         }
      }
   }
   cout << product << endl;
}
//主块
int main() {
   //创建筛子
   createsieve();
   int n = 5, k = 2;
   int arr[n] = { 2, 3, 11, 13, 23 };
   productOfKthPrimes(arr, n, k);  
   return 0;
}

输出结果

39

以上是 C ++数组中每个第K个素数的乘积 的全部内容， 来源链接： utcz.com/z/316378.html

回到顶部