Độ chênh tuyệt đối giữa tích số nguyên tố và không nguyên tố trong mảng

Ở đây chúng ta sẽ xem cách tìm độ chênh tuyệt đối giữa tích của tất cả số nguyên tố và tất cả số không nguyên tố của một mảng. Để giải quyết bài toán này, chúng ta phải kiểm tra xem một số có phải nguyên tố hay không. Một cách có thể để kiểm tra nguyên tố là kiểm tra 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 O(√n) thời gian. Sau đó lấy tích và tìm độ chênh 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);
}

Kết quả

Difference: 125