Cho một số nguyên làm đầu vào. Mục tiêu là kiểm tra số Num có phải số nguyên tố hay không bằng đệ quy.
Để kiểm tra số nguyên tố, duyệt từ i=2 đến i≤Num/2. Nếu có i nào chia hết Num thì Num không phải nguyên tố (số nguyên tố chỉ chia hết cho 1 và chính nó).
Ví dụ
Đầu vào - Num = 32
Đầu ra - 32 không phải số nguyên tố!
Giải thích - Duyệt i=2 đến 16, tại i=2 chia hết → không nguyên tố.
Đầu vào - Num = 43
Đầu ra - 43 là số nguyên tố!
Giải thích - Duyệt i=2 đến 21, không i nào chia hết → là nguyên tố.
Phương pháp sử dụng trong chương trình dưới đây
Dùng hàm đệ quy checkPrime(int num1, int index) nhận số và chỉ số index chạy từ 2 đến num1/2.
Cơ sở: num1 < 2 trả về 0 (không nguyên tố). num1 == 2 hoặc 3 trả về 1 (nguyên tố).
Nếu num1 % index == 0 trả về 0. Nếu index ≤ num1/2 trả về 1 (đã kiểm tra hết không chia hết). Ngược lại đệ quy checkPrime(num1, index+1).
Nhập số Num.
Hàm checkPrime(int num1, int index) trả về 1 nếu nguyên tố, 0 nếu không.
Nếu num1 < 2 return 0.
Nếu num1 == 2 hoặc 3 return 1.
Nếu num1 % index == 0 return 0.
Nếu index ≤ num1/2 return 1.
Đệ quy result = checkPrime(num1, index+1); return result.
In kết quả trong main.
Ví dụ mã
#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<<" là số nguyên tố!"; } else{ cout <<Num<<" không phải số nguyên tố!"; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
31 là số nguyên tố!