ผลคูณของทุก K-th Prime Number ในอาร์เรย์ใน C++

ได้รับอาร์เรย์ arr[n] ที่มี n Prime Numbers และ k งานคือหาผลคูณของทุก k-th Prime Number ในอาร์เรย์

เช่น arr[] = {3, 5, 7, 11} และ k = 2 ดังนั้น Prime Number ทุก k คือ 5 และ 11 หาผลคูณได้ 5×11 = 55

Prime Numbers คืออะไร?

Prime Number คือจำนวนธรรมชาติที่หารด้วยตัวอื่นไม่ลง ยกเว้น 1 และตัวมันเอง เช่น 2, 3, 5, 7, 11, 13 ฯลฯ

ตัวอย่าง

Input: arr[] = {3, 5, 7, 11, 13} k=2
Output: 55
คำอธิบาย: ทุก 2nd Element คือ 5 และ 11 ผลคูณ = 55

Input: arr[] = {5, 7, 13, 23, 31} k=3
Output: 13
คำอธิบาย: ทุก 3rd Element คือ 13 ผลลัพธ์ = 13

วิธีแก้:

รับ Input Array n Elements และ k
สร้าง Sieve สำหรับเก็บ Prime Numbers
ท่อง Array หา k-th Element คูณกับ Product Variable แบบ Recursive สำหรับทุก k-th Element
พิมพ์ Product

อัลกอริทึม

Start
Step 1: Define MAX 1000000
Step 2: Define bool prime[MAX + 1]
Step 3: Function createsieve()
  Call memset(prime, true, sizeof(prime))
  Set prime[1] = false, prime[0] = false
  Loop For p = 2 to p*p <= MAX
    If prime[p] == true
      For i = p*2 to MAX step p
        Set prime[i] = false

Step 4: Function productOfKthPrimes(int arr[], int n, int k)
  Set c = 0, product = 1
  Loop For i = 0 to n-1
    If prime[arr[i]]:
      Increment c
      If c % k == 0:
        product *= arr[i]
        c = 0
  Print product

Step 5: Main()
  Call 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 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;
        }
    }
}

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;
}