Để kiểm tra xem hai số a và b có phải là hai nguyên tố cùng nhau hay không, chúng ta có thể sử dụng thuật toán Euclid để tìm ước chung lớn nhất (UCLN) của hai số đó. Nếu UCLN của a và b bằng 1, thì a và b được coi là hai số nguyên tố cùng nhau.
Bài trước:
Bài 28 chuẩn hoá xâu trong c++
1. Số nguyên tố cùng nhau là gì?
Trong toán học, hai số nguyên a và b (khác 0) được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất (UCLN) của chúng bằng 1.
Ví dụ: 2 và 13 là một cặp số nguyên tố cùng nhau vì UCLN(2,13) = 1
2. Cách tìm số nguyên tố cùng nhau
Để kiểm tra xem hai số nguyên có phải là nguyên tố cùng nhau hay không, ta sử dụng thuật toán tìm ước chung lớn nhất. Một thuật toán phổ biến để tìm UCLN là thuật toán Euclid.
2.1. Bài toán: Kiểm tra hai cố có nguyên tố cùng nhau
Bài 29 (TH-CSLT-01): Trong toán học, các số nguyên a và b (hai số khác 0), được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất là 1. Ví dụ, 2 và 13 là nguyên tố cùng nhau vì ước số chung lớn nhất của chúng là 1.
Hãy viết chương trình con xác định 02 số (a, b) (được nhập từ bàn phím) có phải là số nguyên cùng nhau hay không? Sau đó viết chương trình để thực hiện việc nhập các số, kiểm tra và đưa ra thông báo tương ứng (có phải là số nguyên tố cùng nhau hoặc không).
Chú ý: cần viết thêm chương trình con xác định ước số chung lớn nhất để bổ trợ
2.2. Ý tưởng thuật toán
2.2.1. Hàm tìm ước chung lớn nhất
- Nếu a = 0 hoặc b = 0, thì UCLN(a,b) là tổng của a và b.
- Áp dụng thuật toán Eculid để lặp lại phép trừ hoặc chia cho đến khi tìm được ước chung lớn nhất: Sử dụng vòng lặp while, nếu a>b thì a=a-b; ngược lại b=b-a. Lặp cho đến khi a bằng b. Khi đó ước chung lớn nhất của hai số a và b là a.
Bạn có thể tham khảo thêm cách tìm ước khác qua bài kiểm tra số hoàn hảo c++.
2.2.2. Hàm kiểm tra số nguyên tố cùng nhau c++
- Kiểm tra nếu ước chung lớn nhất UCLN(a,b) = 1 của hai số a và b bằng 1 thì trả về true (là nguyên tố cùng nhau), ngược lại trả về false(không phải là nguyên tố cùng nhau).
2.3. Chương trình c++: Kiểm tra số nguyên tố cùng nhau
#include<iostream>
using namespace std;
//Tìm ước chung lớn nhất
int UCLN(int a,int b){
if(a==0 || b==0){
return a+b;
}
while(a!=b){
if(a>b){
a=a-b;
}else{
b=b-a;
}
}
return a;
}
// Xac dinh so nguyen to cung nhau
bool coprime(int a, int b){
if(UCLN(a,b)==1){
return true;
}
return false;
}
int main(){
int a,b;
cout<<"Nhap so nguyen a: "; cin>>a;
cout<<"Nhap so nguyen b: "; cin>>b;
if(coprime(a,b)){
cout<<a<<" va "<<b<<" la hai so nguyen to cung nhau";
}else{
cout<<a<<" va "<<b<<" khong la hai so nguyen to cung nhau";
}
}
2.4. Kết quả chạy chương trình
Trên đây là đoạn mã đơn giản để xác định 02 số (a, b) (được nhập từ bàn phím) có phải là nguyên cùng nhau hay không? . Cảm ơn các bạn đã theo dõi trên ttnguyen.net
Tải full bài tập thực hành C/C++ có lời giải:
Bài viết cùng chủ đề:
