给出 n 个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
有多组测试数据，每组测试数据有两行。
第一行为一个整数 n (n <= 600)。
在第二行中有 n 个以空格分隔的不同的整数（大于等于 1 且小于等于 10, 000）。
当 n = 0 时，程序结束，不需要处理这组数据。
每行输出最简真分数组合的个数
7
3 5 7 9 11 13 15
3
2 4 5
0
17
2
思想：辗转相除法
#include<iostream>//初级
using namespace std;
int main(){
int n;
while(cin>>n){
if(n==0){
break;
}
int i,j,k,p,num=0;
int m[n];
for(i=0;i<n;i++){
cin>>m[i];
}
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
if(m[i]>m[j]){
p=m[i];
}
else{
p=m[j];
}
for(k=2;k<=p;k++){
if(m[i]%k==0&&m[j]%k==0){
break;
}
}
if(k>m[j]){
num=num+1;
}
}
}
cout<<num<<endl;
}
return 0;
}
升级版
1 #include<iostream> 2 using namespace std; 3 int num(int p,int q){//辗转相除法 4 if(q==0){ 5 return p; 6 } 7 else{ 8 return num(q,p%q); 9 } 10 } 11 int main(){ 12 int n; 13 while(cin>>n){ 14 if(n==0){ 15 break; 16 } 17 int i,j; 18 int m[n]; 19 for(i=0;i<n;i++){ 20 cin>>m[i]; 21 } 22 int sum=0; 23 for(i=0;i<n;i++){ 24 for(j=i+1;j<n;j++){ 25 if(num(m[i],m[j])==1){ 26 sum=sum+1; 27 } 28 } 29 } 30 cout<<sum<<endl; 31 } 32 return 0; 33 }
原文：https://www.cnblogs.com/zq-dmhy/p/11060693.html