AOJ737关于最大公约数的疑惑

Description小光是个十分喜欢素数的人有一天他在学习最大公约数的时候突然想到了一个问题他想知道从1到n这n个整数中有多少对最大公约数为素数的 Description 小光是个十分喜欢素数的人有一天他在学习最大公约数的时候突然想到了一个问题他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)即有多少(x,y),gcd(x,y)素数1#include #include using namespace std;const int maxn 100000 5;bool check[maxn];int phi[maxn];int prime[maxn];int tot;//Kuangbin模板void getEuler(){memset(check, false, sizeof(check));phi[1] 1;tot 0;for(int i 2; i 转:https://www.cnblogs.com/wiklvrain/p/8179480.html