Độ chênh tuyệt đối giữa tổng 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ổng 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ổng và tìm độ chênh tuyệt đối.

Thuật toán

diffPrimeNonPrimeSum(arr)

begin
  sum_p := sum of all prime numbers in arr
  sum_np := sum of all non-prime numbers in arr
  return |sum_p – sum_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 diffPrimeNonPrimeSum(int arr[], int n) {
  int sum_p = 0, sum_np = 0;
  for(int i = 0; i<n; i++){
    if(isPrime(arr[i])){
      sum_p += arr[i];
    } else {
      sum_np += arr[i];
    }
  }
  return abs(sum_p - sum_np);
}

main() {
  int arr[] = { 5, 8, 9, 6, 21, 27, 3, 13};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Difference: " << diffPrimeNonPrimeSum(arr, n);
}

Kết quả

Difference: 50