ความต่างสัมบูรณ์ระหว่างผลคูณจำนวนเฉพาะและไม่ใช่จำนวนเฉพาะในอาร์เรย์

ที่นี่เราจะดูวิธาหาความต่างสัมบูรณ์ระหว่างผลคูณของจำนวนเฉพาะทั้งหมด และผลคูณของจำนวนที่ไม่ใช่จำนวนเฉพาะทั้งหมดในอาร์เรย์ ตรวจสอบจำนวนเฉพาะด้วยการเช็คตัวหารจาก 2 ถึงรากที่สอง ใช้เวลา O(√n) แล้วหาผลคูณและความต่างสัมบูรณ์

อัลกอริทึม

diffPrimeNonPrimeProd(arr)

begin
    prod_p := product of all prime numbers in arr
    prod_np := product of all non-prime numbers in arr
    return |prod_p - prod_np|
end

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

int diffPrimeNonPrimeProd(int arr[], int n) {
    int prod_p = 1, prod_np = 1;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i]))
            prod_p *= arr[i];
        else
            prod_np *= arr[i];
    }
    return abs(prod_p - prod_np);
}

int main() {
    int arr[] = {4, 5, 3, 8, 13, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Difference: " << diffPrimeNonPrimeProd(arr, n);
}

ผลลัพธ์

Difference: 125