Ở đây chúng ta sẽ xem cách đếm số cặp đồng nguyên tố từ phạm vi, trong đó một số sẽ không xuất hiện nhiều hơn một cặp.
Trước khi thảo luận về logic, chúng ta hãy xem các số đồng nguyên tố là gì? Các số đồng nguyên tố là những số chỉ có một ước số nguyên dương, đó là 1. Nói cách khác, ta có thể nói GCD của hai số này là 1.
Ở đây chúng tôi đang cung cấp giới hạn dưới và giới hạn trên. Nếu giới hạn dưới và giới hạn trên là 1 và 6, thì có ba cặp. Đây là (1, 2), (3, 4) và (5, 6)
Phương pháp giải bài toán này là như vậy:Nếu các số liên tiếp nhau thì chúng luôn đồng nguyên tố. Vì vậy, số đếm sẽ là (R - L + 1) / 2. Nếu (R - L + 1) là số lẻ thì sẽ còn lại một số, đó sẽ không được xếp vào bất kỳ cặp nào, nếu là chẵn thì tất cả sẽ tạo thành một cặp
Thuật toán
countCoPrimePairs (L, R)
Begin return (R – L + 1)/2 End
Ví dụ
#include <iostream>
using namespace std;
int countCoPrimePairs(int L, int R) {
return (R - L + 1)/2;
}
main() {
int l = 1, r = 6;
cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
} Đầu ra
Number of co-prime pairs: 3