เราได้รับจำนวนเต็มเป็นอินพุต เป้าหมายคือการค้นหาว่าตัวเลขอินพุต Num เป็นจำนวนเฉพาะหรือไม่ใช่เฉพาะโดยใช้การเรียกซ้ำ
หากต้องการตรวจสอบว่าตัวเลขเป็นจำนวนเฉพาะหรือไม่ ให้เริ่มเดินทางจาก i=2 ถึง i<=Num/2 หาก i ตัวใดตัวหนึ่งหารด้วย Num ลงตัว ตัวเลขนั้นก็ไม่ใช่จำนวนเฉพาะ เนื่องจากจำนวนเฉพาะหารด้วย 1 ลงตัวและตัวตัวเลขนั้นเอง
ตัวอย่าง
ป้อนข้อมูล − Num =32
ผลผลิต − 32 ไม่ใช่ Prime!
คำอธิบาย − หากเราเริ่มเดินทางจาก i=2 ไปยัง i<=32/2 จากนั้นในตอนแรกมันจะหารด้วย 2 ลงตัวซึ่งบอกว่าไม่ใช่ไพรม์
ป้อนข้อมูล − Num =43
ผลผลิต − 43 เป็นจำนวนเฉพาะ!
คำอธิบาย − หากเราเริ่มเดินทางจาก i=2 ถึง i<=43/2 มันจะหารด้วยจำนวนใด ๆ ระหว่าง 2 ถึง 21 ไม่ได้ ซึ่งบอกว่าเป็นจำนวนเฉพาะ
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางนี้ เรากำลังใช้ฟังก์ชันเรียกซ้ำ checkPrime(int num1, int index) ซึ่งรับค่าตัวเลขและดัชนีที่จะรับค่าตั้งแต่ 2 ถึง num1/2
สำหรับกรณีฐาน-:ถ้า num1<2 คืนค่า 1 เนื่องจากไม่ใช่ไพรม์
ถ้า num1==2 คืนค่า 2 เนื่องจากเป็นจำนวนเฉพาะ
อื่น:- if(index<=num1/2) แล้วเราถึงจุดที่ไม่มีการหารดัชนี num1 อย่างสมบูรณ์ ดังนั้นให้คืนค่า 1 เนื่องจากเป็นไปได้สำหรับจำนวนเฉพาะเท่านั้น มิฉะนั้น เรียกซ้ำสำหรับดัชนีถัดไปโดยใช้ result=checkPrime(num1, index+1 )
-
ใช้หมายเลขอินพุต Num
-
ฟังก์ชัน checkPrime(int num1,int index) รับอินพุตและส่งกลับ 1 หากตัวเลขเป็นจำนวนเฉพาะ มิฉะนั้นจะคืนค่า 0
-
ถ้า num1<2 คืนค่า 0 เนื่องจากตัวเลขที่น้อยกว่า 2 ไม่ใช่จำนวนเฉพาะ
-
ถ้า num1 เป็น 2 หรือ 3 ให้คืนค่า 1 เนื่องจาก 2 และ 3 เป็นจำนวนเฉพาะ
-
หากดัชนี num1% คือ <=num1/2 ให้คืนค่า 1 เป็นไม่เกิน num1/2 ไม่มีตัวเลขใดถูกหารทั้งหมด num1 ดังนั้น num1 จึงเป็นจำนวนเฉพาะ
-
เรียกซ้ำสำหรับดัชนีถัดไปโดยใช้ result=checkPrime(num1, index+1)
-
ส่งคืนผลลัพธ์
-
ผลการพิมพ์ที่ได้รับภายใน main.
ตัวอย่าง
#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!
