โปรแกรมเรียกซ้ำตรวจสอบจำนวนเฉพาะใน C++

ภาพรวม

ได้รับจำนวนเต็มเป็นอินพุต เป้าหมายคือตรวจสอบว่า Num เป็นจำนวนเฉพาะ (Prime) หรือไม่ใช่จำนวนเฉพาะ (Non-prime) โดยใช้การเรียกซ้ำ

วิธีตรวจสอบ: วนจาก i=2 ถึง i<=Num/2 หากมี i ใดหาร Num ลงตัว แสดงว่าไม่ใช่จำนวนเฉพาะ เพราะจำนวนเฉพาะหารได้เฉพาะ 1 และตัวมันเอง

ตัวอย่าง

อินพุต − Num = 32

เอาต์พุต − 32 is non-Prime!

คำอธิบาย − วน i=2 ถึง 16 พบว่า 32 หาร 2 ลงตัว จึงไม่ใช่จำนวนเฉพาะ

อินพุต − Num = 43

เอาต์พุต − 43 is a Prime number!

คำอธิบาย − วน i=2 ถึง 21 ไม่มีตัวใดหาร 43 ลงตัว จึงเป็นจำนวนเฉพาะ

แนวทางการแก้ปัญหา

ใช้ฟังก์ชันเรียกซ้ำ checkPrime(int num1, int index) รับตัวเลขและดัชนีที่จะทดสอบจาก 2 ถึง num1/2

Base case: หาก num1 < 2 คืน 0 (ไม่ใช่เฉพาะ) หาก num1 == 2 หรือ 3 คืน 1 (เป็นเฉพาะ)

Recursive: หาก num1 % index == 0 คืน 0 หาก index > num1/2 คืน 1 (ไม่พบตัวหาร) มิฉะนั้น เรียก checkPrime(num1, index+1)

• รับตัวเลข Num
• ฟังก์ชัน checkPrime(int num1, int index) คืน 1 ถ้าเป็นเฉพาะ 0 ถ้าไม่ใช่
• หาก num1 < 2 คืน 0
• หาก num1 == 2 หรือ 3 คืน 1
• หาก num1 % index == 0 คืน 0
• หาก index > num1/2 คืน 1
• มิฉะนั้น เรียกซ้ำ checkPrime(num1, index+1)
• พิมพ์ผลลัพธ์ใน main

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

int checkPrime(int num1, int index){ 
    if (num1 < 2){ 
        return 0; 
    } 
    if (num1 == 2 || num1 == 3){ 
        return 1; 
    } 
    if (num1 % index == 0){ 
        return 0; 
    } 
    if (index > num1 / 2){ 
        return 1; 
    } 
    int result = checkPrime(num1, index + 1); 
    return result; 
} 

int main(){ 
    int Num = 31; 
    if (checkPrime(Num, 2) == 1){ 
        cout << Num << " is a Prime number!"; 
    } else { 
        cout << Num << " is non Prime!"; 
    } 
    return 0; 
}

ผลลัพธ์

31 is a Prime number!