อภิปรายปัญหาที่เราได้รับตัวเลข N และเราต้องแยกตัวเลขนี้เป็นผลรวมของจำนวนเฉพาะมากที่สุด ตัวอย่างเช่น:
Input: N = 7 Output: 2 2 3 คำอธิบาย: 7 สามารถแสดงเป็นผลรวมของสอง 2 และหนึ่ง 3 ซึ่งเป็นจำนวนเฉพาะมากที่สุด Input : N = 17 Output: 2 2 2 2 2 2 2 3
วิธีการหาคำตอบ
เพื่อแสดงตัวเลขในจำนวนเฉพาะ เราสามารถลบจำนวนเฉพาะกับ N และตรวจสอบความต่างว่าเป็นจำนวนเฉพาะหรือไม่ ถ้าความต่างเป็นจำนวนเฉพาะ เราสามารถแสดง N เป็นผลรวมของจำนวนเฉพาะสองตัว
แต่ที่นี่ เราต้องหาจำนวนเฉพาะมากที่สุด และสำหรับนั้น เราควรใช้จำนวนเฉพาะน้อยที่สุด คือ 2 และ 3 เราสามารถสร้างตัวเลขใดๆ ด้วยผลรวมของ 2 และ 3
- ตรวจสอบตัวเลขว่าเป็นเลขคู่ ถ้าเป็นคู่ สามารถสร้างได้จากผลรวมของ (N/2) ตัว 2
- ถ้าเป็นคี่ สามารถสร้างได้จากหนึ่ง 3 และ [(N-3)/2] ตัว 2
- ด้วยวิธีนี้ เราสามารถแสดง N ด้วยผลรวมของจำนวนเฉพาะมากที่สุด
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int N = 7;
// ตรวจสอบว่า N เป็นคี่
// ถ้าใช่ พิมพ์ 3 และลบ 3 จาก N
if (N & 1 == 1) {
cout << "3 +";
N -= 3;
}
// ต่อไปลบและพิมพ์ 2 จนกว่า N จะเป็น 0
while (N != 2) {
cout << " 2 +";
N -= 2;
}
cout << " 2";
return 0;
}ผลลัพธ์
3 + 2 + 2
สรุป
ในบทช่วยสอนนี้ เราอภิปรายการแสดงตัวเลขเป็นผลรวมของจำนวนเฉพาะมากที่สุด เราอภิปรายวิธีง่ายๆ ในการแก้ปัญหานี้โดยการแสดงตัวเลขเป็นผลรวมของ 2 และ 3 เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์
