关于最大公约数的疑惑

Description

小光是个十分喜欢素数的人，有一天他在学习最大公约数的时候突然想到了一个问题，他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)，即有多少(x,y),gcd(x,y)=素数，1<=x,y<=n。但是小光刚刚接触最大公约数，不能解决这个问题，于是他希望你能帮助他解决这个问题。

Input

一个整数N  (1<=N<=10^5)

Output

(x,y)的个数

Sample Input

5

Sample Output

5

HINT

(2,2) (2,4) (4,2) (3,3) (5,5)

Source

#include<iostream> using namespace std; int a[100010]={0}; int ss(int x) { int i,j; if (a[x]){ return 1; } for (i=2; i<x; i++) { if (x%i==0) break; } if (x==i) { a[x] = 1; return 1; } return 0; } int gcd(int x,int y) { int t; if (x<y) { t=x; x=y; y=t; } while (y) { t = x%y; x=y; y=t; } return x; } int main() { int n,i,j,cnt=0; cin>>n; for (i=2; i<=n; i++) { if (ss(i)) { cnt++; } for (j=2; j<=n; j++) { if (i==j) { continue; } if (ss(gcd(i,j))) { cnt++; } } } cout<<cnt<<endl; return 0; }