有多少数互质

　

互质

有多少数互质

Description

从1到n中，任意选择两个数，使其互质，互质即为两个数最大公约数为1。问总共有多少种选择方法，注意（1，2）和（2，1）是同一种方案（互质是公约数只有1的两个整数，叫做互质整数。）

Input

输入第一行输入T（T<=100000） 接下来每一行输入一个n，(1<=n<=1000)

Output

每一行输出一个方案数

Sample Input

1

2

Sample Output

1

#include<stdio.h>
int huzhi(int a, int b);
int main(){
	int i,j,m,n,count=0,k;
	scanf("%d\n",&n);
	int b[n];
	for(k=0;k<n;k++){	
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		for(j=i+1;j<=m;j++){
			if(huzhi(i,j)==1) count++;
		}
	}
	b[k]=count;
	count=0;
 }
	for(i=0;i<n;i++){
		printf("%d\n",b[i]);
	}
	return 0;
}
int huzhi(int a, int b){
	int t;
	while(b!=0){
		t=a%b;
		a=b;
		b=t;
	}
   return a;
}

文章最后发布于: 2019-05-17 23:23:22

相关阅读

互质数的个数

给定一个整数 nn，请问有多少个整数 i满足条件：gcd(i, n) = 1，1<=i<=n; 输入格式 输入一行，输入一个整数 n(n<=10^9)。 输出格式