Convenim să spunem că un număr natural nenul x este special dacă pentru toţi divizorii d ai lui x, valoarea d+x/d este număr prim.
Să analizăm numărul natural 10. Divizorii săi sunt 1, 2, 5 şi 10. Dacă vom calcula valorile d+x/d, vom obţine 1+10/1= 11, 2+10/2=7, 5+10/5=7, 10+10/10=11 şi observăm că toate aceste valori obţinute sunt numere prime. În concluzie, numărul 10 este special.
Analizând în mod similar numărul 4, constatăm că el nu îndeplineşte condiţia prezentată anterior deoarece divizorii săi sunt 1, 2 şi 4. În urma verificărilor efectuate, obţinem: 1+4/1=5 (prim), 2+4/2=4 (neprim), 4+4/4=5 (prim).
Cerinţă
Scrieţi un program care determină numărul de numere naturale nenule mai mici sau egale cu n care sunt speciale.
Date de intrare
Pe prima linie a fişierului numere11.in se găseşte numărul natural n.
Date de ieşire
Fişierul numere11.out va conţine un număr natural reprezentând numărul de numere naturale nenule mai mici sau egale cu n care sunt speciale.
Restricţii
• 0 < n ≤ 500000
Exemple
numere11.in
numere11.out
Explicaţii
20
4
Există 4 numere mai mici sau egale decât 20 care sunt speciale. Acestea sunt: 1, 2, 6, 10
1+1/1=2 (prim);
1+2/1=3(prim), 2+2/2=3 (prim);
1+6/1=7(prim), 2+6/2=5(prim), 3+6/3=5(prim), 6+6/6=7(prim);
1+10/1= 11(prim), 2+10/2=7(prim), 5+10/5=7(prim), 10+10/10=11(prim).