1490: 关于最大公约数的疑惑
时间限制: 1 Sec
内存限制: 128 MB
提交: 11
解决: 9
上一题
提交
状态
下一题
题目描述
小光是个十分喜欢素数的人，有一天他在学习最大公约数的时候突然想到了一个问题，他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)，即有多少(x,y),gcd(x,y)=素数，1<=x,y<=n。但是小光刚刚接触最大公约数，不能解决这个问题，于是他希望你能帮助他解决这个问题。
输入
一个整数N (1<=N<=10^5)
输出
(x,y)的个数
样例输入
5
样例输出
5
提示
(2,2) (2,4) (4,2) (3,3) (5,5)
#include <iostream>
#include <cstdio>
using namespace std;
int zui(int a, int b){
int c;
if(a<b)
{
c=a;
a=b;
b=c;
}
while(b){
c=a;
a=b;;
b=c%b;
}
return a;
}
int shu(int n){int i;
for(i=2;i<n;i++){
if(n%i==0)
break;
}
if(i==n)
return 1;
return 0;
}
int main(){
long n;
long i,j;
long sum=0;
scanf("%ld", &n);
for(i=2;i<=n;i++){
if(shu(i))sum++;
for(j=2;j<=n;j++){
if(i==j)continue;
if(shu(zui(i,j)))
sum++;
}
}
printf("%d", sum);
return 0;
}
