Aromatic plants

0.55 A friend of Professor Oak suggested him including some aromatic plants in his garden, and Prof. Oak thought that it was such a good idea. As you can see, now he has 11 such plants: 5 in the top row, and 6 in the bottom row. Hmm... so we have a prime number and a composite number that add up to a prime number. How common is that?

0.40

Input

Input consists of several cases, each with an integer $n$ between 2 and $10^7$ .

Output

For every $n$ , print the number of triples of integer numbers $(a, b, c)$ such that:

the three numbers are between 2 and $n$ ,
$a$ is prime, $b$ is composite, $c$ is prime,
and $a + b = c$ .

Problem information

Author: Salvador Roura
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-10T18:32:17.892Z