.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » numere11

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
numere11


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

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.innumere11.outExplicaţ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).

autor: Prof. Cornelia Ivaşc
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
Chestionare recomandate
surse trimise | ajutor