Chúng tôi được cung cấp một số nguyên làm đầu vào. Mục đích là để tìm xem số đầu vào Num là số nguyên tố hay không phải số nguyên tố bằng cách sử dụng đệ quy.
Để kiểm tra xem một số có phải là số nguyên tố hay không, hãy bắt đầu chuyển từ i =2 đến i <=Num / 2. Nếu bất kỳ i nào chia hết cho Num thì số đó không phải là số nguyên tố vì các số nguyên tố chỉ chia hết cho 1 và chính số đó.
Ví dụ
Đầu vào - Số =32
Đầu ra - 32 không phải là Nguyên tố!
Giải thích - Nếu chúng ta bắt đầu chuyển từ i =2 đến i <=32/2, thì lúc đầu nó sẽ chia hết cho 2, điều này cho biết nó không phải là số nguyên tố.
Đầu vào - Số =43
Đầu ra - 43 là một số Nguyên tố!
Giải thích - Nếu chúng ta bắt đầu chuyển từ i =2 đến i <=43/2, thì nó sẽ không chia hết cho bất kỳ số nào từ 2 đến 21. Điều này cho biết nó là số nguyên tố.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi đang sử dụng hàm đệ quy checkPrime (int num1, int index) nhận số đầu vào và chỉ mục sẽ nhận các giá trị từ 2 đến num1 / 2.
Đối với trường hợp cơ sở-:if num1 <2 trả về 1 vì nó không phải là số nguyên tố.
Nếu num1 ==2 trả về 2 vì nó là số nguyên tố.
Khác:- if (index <=num1 / 2) thì chúng ta đã đạt đến điểm tối đa mà không có chỉ mục nào chia hết num1 nên trả về 1 vì chỉ có thể cho các số nguyên tố. )
-
Lấy số đầu vào Num
-
Hàm checkPrime (int num1, int index) nhận đầu vào và trả về 1 nếu số là số nguyên tố khác trả về 0.
-
Nếu num1 <2 trả về 0 vì các số nhỏ hơn 2 không phải là số nguyên tố.
-
Nếu num1 là 2 hoặc 3, trả về 1 là 2 và 3 là số nguyên tố.
-
Nếu chỉ số num1% là <=num1 / 2 thì trả về 1 dưới dạng tối đa num1 / 2 không có số nào chia hết num1 nên num1 là số nguyên tố
-
Đệ quy cho chỉ mục tiếp theo bằng cách sử dụng result =checkPrime (num1, index + 1).
-
Trả về kết quả.
-
In kết quả nhận được bên trong main.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
31 is a Prime number!