Sự khác biệt tuyệt đối giữa Tổng của các số không phải số nguyên tố và 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ổng của tất cả các số nguyên tố và tất cả các số không phải là số 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 tổng và cố gắng tìm ra sự khác biệt 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);
}

Đầu ra

Difference: 50