แสดงเลขคี่เป็นผลรวมของจำนวนเฉพาะใน C++

ในปัญหานี้ เราได้รับเลขคี่ N หน้าที่ของเราคือ แสดงเลขคี่เป็นผลรวมของจำนวนเฉพาะ

สามารถมีตัวเลขเฉพาะได้สูงสุดสามจำนวนในขณะที่แสดงตัวเลข

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: ไม่มี =55

ผลลัพธ์: 53 + 2

แนวทางแก้ไข:

เลขคี่สามารถแสดงเป็นผลรวมของจำนวนเฉพาะได้ เมื่อพิจารณาจำนวนเฉพาะเหล่านี้แล้ว เรามีสามกรณี

กรณีที่ 1: ถ้า n เป็นจำนวนเฉพาะ จะแสดงเป็นผลรวมของจำนวนเฉพาะ n .
กรณีที่ 2: ถ้า (n - 2) เป็นจำนวนเฉพาะ จะแสดงเป็นผลรวมของจำนวนเฉพาะสองจำนวน n-2 และ 2 .

กรณีที่ 3: ( n - 3 ) เป็นจำนวนคู่ซึ่งสามารถแสดงเป็นผลรวมของจำนวนเฉพาะสองตัวโดยใช้วิธีการคาดเดาของ Goldbach ซึ่งเราจะตรวจสอบว่าจำนวน A เป็นจำนวนเฉพาะและจำนวน {(n-3) - A } เป็นจำนวนเฉพาะหรือไม่ พิมพ์ค่ะ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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;
}

ผลลัพธ์ -

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