Biểu thị một số lẻ dưới dạng tổng các số nguyên tố trong C ++

Trong bài toán này, chúng ta được cho một số lẻ N. Nhiệm vụ của chúng ta là biểu thị một số lẻ dưới dạng tổng các số nguyên tố.

Có thể có tối đa ba số nguyên tố trong khi biểu thị số.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: N =55

Đầu ra: 53 + 2

Phương pháp tiếp cận giải pháp:

Số lẻ có thể được biểu diễn dưới dạng tổng các số nguyên tố. Xem xét các số nguyên tố này, chúng ta có ba trường hợp.

Trường hợp 1: Nếu n là số nguyên tố, nó được biểu diễn dưới dạng tổng của một số nguyên tố n .
Trường hợp 2: Nếu (n - 2) là số nguyên tố, nó được biểu diễn dưới dạng tổng của hai số nguyên tố n-2 và 2 .

Trường hợp 3: (n - 3) là một số chẵn có thể được biểu diễn dưới dạng tổng của hai số nguyên tố bằng cách sử dụng phương pháp phỏng đoán Goldbach, trong đó chúng ta sẽ kiểm tra xem một số A có phải là số nguyên tố hay không và số {(n-3) - A} cũng là số nguyên tố thì in nó.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <iostream>
using namespace std;

bool isPrime(int x)
{
   if (x == 0 || x == 1)
      return false;
   for (int i = 2; i * i <= x; ++i)
      if (x % i == 0)
         return false;  
   return true;
}

void primeAsSumofPrime(int n) {
   
   if (isPrime(n) )
      cout<<n;
   else if (isPrime(n - 2))
      cout<<"2 "<<"+ "<<(n - 2);
   else{
      cout<<"3 "<<"+ ";
      n -= 3;
      for (int i = 0; i < n; i++) {
         if (isPrime(i) && isPrime(n - i)) {
            cout<<i<<" + "<<(n - i);
            break;
         }
      }
   }
}

int main() {
   
   int n = 561;
   cout<<"The number "<<n<<" expressed as sum of primes is ";
   primeAsSumofPrime(n);
   return 0;
}

Đầu ra -

The number 561 expressed as sum of primes is 3 + 11 + 547