# 牛客Harder Gcd Problem

1. 质数与它的倍数
2. 两个相同质数的倍数

AC代码：
``````#includeiostream
#includealgorithm
#includevector
#includeutility
using namespace std;
const int MAX_N = 2e5 + 5;
typedef pairint, int pint;
bool vis[MAX_N];
bool isnotprime[MAX_N];
int prime[MAX_N];
int main()
{
isnotprime[0] = isnotprime[1] = true;
for (int i = 2; i  MAX_N; i++)
{
if (!isnotprime[i])prime[++prime[0]] = i;
for (int j = 1; j = prime[0]  i * prime[j]  MAX_N; j++)
{
isnotprime[i * prime[j]] = true;
if (i % prime[j] == 0)break;
}
}
int T;
cin  T;
while (T--)
{
fill(vis, vis + MAX_N, false);
int n;
cin  n;
int index = upper_bound(prime + 1, prime + prime[0] + 1, n / 2)-prime;
vectorpint ans;
for (int i = index-1; i = 1; i--)
{
vectorint now;
for (int j = prime[i]; j = n; j+=prime[i])
if (!vis[j])now.push_back(j);
if (now.size() == 1)continue;
if (now.size()  1)now.erase(now.begin() + 1);//如果是奇数，那么他的2倍一定存在，因为他的二倍不可能被选掉
/*上面if中的语句也可以写成这样
if (prime[i] == 3)now.erase(now.begin() + 1);
else now.erase(now.begin() + 2);
*/
for (int j = 0; j+1  now.size(); j+=2)
{
ans.push_back(pint(now[j], now[j + 1]));
vis[now[j]] = vis[now[j + 1]] = true;
}
}
cout  ans.size()'\n';
for (int i = 0; i  ans.size(); i++)
{
cout  ans[i].first  " "  ans[i].second  '\n';
}
}
return 0;
}
``````
• 10:44
• --:--
• 01:14:01
• 02:55