0228. Prime Sum

Input file name:	prime.in
Output file name:	prime.out
Time limit:	750 ms
Memory limit:	64 megabytes

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 file

The input of the problem consists of the only integer N (1 ≤ N ≤ 10⁶).

Output file

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).

Example:

prime.in	prime.out
4	0

Source: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Discuss       Submit a solution



Printable version