CF449C Jzzhu and Apples

Jzzhu 从他的大苹果树上摘了 $n$ 个苹果。所有苹果编号从 $1$ 到 $n$。现在他想把这些苹果卖给一家苹果商店。 Jzzhu 会将苹果打包成若干组然后出售。每一组必须包含两个苹果，并且每组中两个苹果编号的最大公约数必须大于 $1$。当然，每个苹果最多只能属于一个分组。 Jzzhu 想知道，他最多能分成多少组。你能帮帮他吗？

一个整数 $n$，表示苹果的数量。$1 \leq n \leq 10^5$。

第一行输出一个整数 $m$，表示最多可以分成的分组数。接下来的 $m$ 行中，每行输出两个整数，表示当前分组中两个苹果的编号。 如果有多种最优方案，可以输出任意一种。

由 ChatGPT 5 翻译