Sự khác biệt tuyệt đối giữa Tích của các số không nguyên tố và các số nguyên tố của một mảng?

Ở đây chúng ta sẽ thấy cách chúng ta có thể tìm thấy sự khác biệt tuyệt đối giữa tích của tất cả các số nguyên tố và tất cả các số không nguyên tố của một mảng. Để giải quyết vấn đề này, chúng ta phải kiểm tra xem một số có phải là số nguyên tố hay không. Một cách khả thi để kiểm tra tính nguyên thủy là kiểm tra một số không chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của số đó. Vì vậy, quá trình này sẽ mất 𝑂 (√𝑛) lượng thời gian. Sau đó, lấy sản phẩm và cố gắng tìm ra sự khác biệt tuyệt đối.

Thuật toá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

Ví dụ

#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; //not prime
      }
   }
   return true; //prime
}
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);
}
main() {
   int arr[] = { 4, 5, 3, 8, 13, 10};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Difference: " << diffPrimeNonPrimeProd(arr, n);
}

Đầu ra

Difference: 125