Tích của mọi số nguyên tố thứ K trong một mảng trong C ++

Cho một mảng arr [n] chứa n số nguyên tố và k; nhiệm vụ là tìm tích của mọi số nguyên tố thứ k trong một mảng.

Giống như, chúng ta có một mảng arr [] ={3, 5, 7, 11} và k =2 vì vậy số nguyên tố sau mỗi k tức là 5 và 11, chúng ta phải tìm tích của chúng sẽ là 5x11 =55 và in kết quả dưới dạng đầu ra.

Số nguyên tố là gì?

Số nguyên tố là một số tự nhiên không thể chia cho bất kỳ số nào khác ngoại trừ 1 hoặc chính số đó. Một số số nguyên tố là 2, 3, 5, 7, 11, 13, v.v.

Ví dụ

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.

Phương pháp tiếp cận mà chúng tôi sẽ sử dụng để giải quyết vấn đề trên -

Lấy một mảng đầu vào gồm n phần tử và k, để tìm tích của mọi phần tử thứ k.
Tạo một cái sàng để lưu trữ các số nguyên tố.
Sau đó, chúng ta phải duyệt qua mảng và lấy phần tử thứ k và nhân nó với biến tích số một cách đệ quy cho mọi phần tử thứ k.
In sản phẩm.

Thuật toán

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void createsieve() {
   memset(prime, true, sizeof(prime));
   // 0 and 1 are not prime numbers
   prime[1] = false;
   prime[0] = false;
   for (int p = 2; p * p <= MAX; p++) {
      if (prime[p] == true) {
         // finding all multiples of p
         for (int i = p * 2; i <= MAX; i += p)
         prime[i] = false;
      }
   }
}
// compute the answer
void productOfKthPrimes(int arr[], int n, int k) {
   // count the number of primes
   int c = 0;
   // find the product of the primes
   long long int product = 1;
   // traverse the array
   for (int i = 0; i < n; i++) {
      // if the number is a prime
      if (prime[arr[i]]) {
         c++;
         if (c % k == 0) {
            product *= arr[i];
            c = 0;
         }
      }
   }
   cout << product << endl;
}
//main block
int main() {
   // create the sieve
   createsieve();
   int n = 5, k = 2;
   int arr[n] = { 2, 3, 11, 13, 23 };
   productOfKthPrimes(arr, n, k);  
   return 0;
}

Tích của mọi số nguyên tố thứ K trong một mảng trong C ++

Ví dụ

Thuật toán

Ví dụ

Đầu ra