[C++] Số nguyên tố cùng nhau – Thuật toán kiểm tra chi tiết

Để 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. Bài toán số 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. Ý tưởng thuật toán

2.1 Chương trình con tìm ước chung lớn nhất

• Kiểm tra nếu a hoặc b bằng 0 thì trả về tổng của a và b.
• 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 Chương trình con kiểm tra số nguyên tố cùng nhau c++

• Kiểm tra nếu ước chung lớn nhất của hai số a và b bằng 1 thì trả về true, ngược lại trả về false.

3. Cài đặt chương trình

#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";
    }

}

4. Kết quả

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

Liên quan:

• sắp xếp số nguyên tố về đầu dãy
• [C++] Tính tổng các số nguyên tố nhỏ hơn N