資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中計算最大公約數為給定數字的自然數對
我們給出三個輸入變數“start”、“end”和“number”。目標是在start和end之間找到最大公約數（GCD）值為“number”的數字對。例如，GCD(A,B)=number，並且A、B都在[start,end]範圍內。
讓我們透過例子來理解。
輸入 − start=5 end=20 number=8
輸出 − 最大公約數為給定數字的自然數對的數量為 − 3
解釋 − 5到20之間，最大公約數為8的數對為 − (8,8), (8,16), (16,8)
輸入 − start=5 end=20 number=7
輸出 − 最大公約數為給定數字的自然數對的數量為 − 2
解釋− 20到30之間，最大公約數為7的數對為 − (21,28), (28,21)
下面程式中使用的方法如下
我們將使用兩種方法。第一種是樸素的方法，我們將使用for迴圈從i=start遍歷到i<=end，內迴圈從j=start遍歷到j<=end。對於每一對(i,j)，檢查GCD(i,j)==number是否成立。如果成立，則計數器加1。
將變數start、end和number作為整數。
函式GCD(int a, int b)是遞迴函式，返回傳遞給它的引數a、b的最大公約數。
如果b不為零，則遞迴呼叫自身為GCD(b,a%b)，否則返回a。
函式GCD_pairs(int start, int end, int number)接受邊界變數start、end和變數number，並返回start和end之間最大公約數為number的數對。
將初始計數設定為0。
使用兩個for迴圈來遍歷每一對的每個成員。外迴圈從i=start遍歷到i<=end，內迴圈從j=start遍歷到j<=end。
檢查對於數對(i,j)，GCD(i,j)==number是否成立。如果成立，則計數器加1。
最後，我們將得到最大公約數為number的數對的總數。
返回計數作為結果。
高效方法
在這種方法中，我們將更新start和end的值。對於數對(i,j)來說，要使最大公約數為number，i和j都應該能被‘number’整除。最多會有(end-start)/number個數字能被‘number’整除。為了得到start和end之間能被‘number’整除的數字，我們將從start = (start + number - 1) / number遍歷到end = end / number；因此，對於每個這樣的數字，如果gcd(i,j)==1，則為這樣的數對(i,j)增加計數。
將變數start、end和number作為整數。
更新start = (start+number - 1)/number。以及end=end/number。
函式GCD(int a, int b)是遞迴函式，返回傳遞給它的引數a、b的最大公約數。
如果b不為零，則遞迴呼叫自身為GCD(b,a%b)，否則返回a。
函式GCD_pairs(int start, int end, int number)接受邊界變數start、end和變數number，並返回start和end之間最大公約數為number的數對。
將初始計數設定為0。
使用兩個for迴圈來遍歷每一對的每個成員。外迴圈從i=start遍歷到i<=end，內迴圈從j=start遍歷到j<=end。
檢查對於數對(i,j)，GCD(i,j)==1是否成立。如果成立，則計數器加1。
最後，我們將得到最大公約數為number的數對的總數。
返回計數作為結果。
示例（樸素方法）
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == number){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of pairs of natural numbers with GCD equal to given number are: 7
示例（高效方法）
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == 1){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
start = (start + number - 1) / number;
end = end / number;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of pairs of natural numbers with GCD equal to given number are: 7
978 次瀏覽
