Jzzhu and Apples

题意翻译

给出正整数n,你要把1-n之间的正整数分成尽可能多组,使得每一组两个数的最大公约数大于1;输出能分成最多组的个数,并按任意顺序输出每组的两个数.

题目描述

Jzzhu has picked $ n $ apples from his big apple tree. All the apples are numbered from $ 1 $ to $ n $ . Now he wants to sell them to an apple store. Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group. Jzzhu wonders how to get the maximum possible number of groups. Can you help him?

输入输出格式

输入格式

A single integer $ n $ $ (1<=n<=10^{5}) $ , the number of the apples.

输出格式

The first line must contain a single integer $ m $ , representing the maximum number of groups he can get. Each of the next $ m $ lines must contain two integers — the numbers of apples in the current group. If there are several optimal answers you can print any of them.

输入输出样例

输入样例 #1

6

输出样例 #1

2
6 3
2 4

输入样例 #2

9

输出样例 #2

3
9 3
2 4
6 8

输入样例 #3

2

输出样例 #3

0

题意翻译

给出正整数n,你要把1-n之间的正整数分成尽可能多组,使得每一组两个数的最大公约数大于1;输出能分成最多组的个数,并按任意顺序输出每组的两个数.