Prime Sum

Problem Description

Find all pairs of prime numbers (A, B) such that A<=B and their sum is also a prime number and does not exceed N.

Input

The input of the problem consists of the only integer N (1<=N<=10^6).

Output

On the first line of the output file write the number of pairs meeting the requirements. Then output all pairs one per line (two primes separated by a space).

Sample test(s)

Input

4

Output

0

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
int n{};
std::cin >> n;
std::vector<bool> visit(n + 1, false);
std::vector<int> prime{};

for(unsigned long i = 2; i < visit.size(); i++) {
if(visit[i]) {
continue;
}
prime.push_back(i);
for(unsigned long j = i * 2; j < visit.size(); j += i) {
visit[j] = true;
}
}

int count = 0;
for(unsigned long i = 1; i < prime.size(); i++) {
if(prime[i] - prime[i - 1] == 2) {
count += 1;
}
}
std::cout << count << std::endl;

for(unsigned long i = 1; i < prime.size(); i++) {
if(prime[i] - prime[i - 1] == 2) {
std::cout << 2 << " " << prime[i - 1] << std::endl;
}
}

return 0;
}