# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
84120391 |
Practice:
JKLover |
449C
- 19
|
C++17 (GCC 7-32)
|
Accepted
|
62 ms
|
2236 KB
|
2020-06-18 05:41:33 |
2020-06-18 05:41:33 |
|
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(int x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(int x, char c)
{
if (x < 0)
putchar('-'), x = -x;
print(x);
putchar(c);
}
const int N = 1e5 + 10;
int n, vis[N], p[N], cnt, rest[N], tot = 0;
vector<pair<int, int> > ans;
void report(int x, int y)
{
ans.push_back(make_pair(x, y));
}
int main()
{
n = read();
for (int i = 3; i <= n; ++i)
if (!vis[i] && i % 2)
{
if (i * 2 <= n)
{
cnt = 0;
for (int j = i; j <= n; j += i)
if (!vis[j])
{
vis[j] = 1;
p[++cnt] = j;
}
swap(p[2], p[cnt]);
for (int k = 2; k <= cnt; k += 2)
report(p[k - 1], p[k]);
if (cnt & 1)
rest[++tot] = p[cnt];
}
else
vis[i] = 1;
}
for (int i = 2; i <= n; ++i)
if (!vis[i])
rest[++tot] = i;
for (int k = 2; k <= tot; k += 2)
report(rest[k - 1], rest[k]);
cout << ans.size() << '\n';
for (auto tmp : ans)
write(tmp.first, ' '), write(tmp.second, '\n');
return 0;
}
Click to see test details