Lista de probleme 10

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Inspectoratul școlar județean organizează un concurs pentru ocuparea strategicului post de fochist. La proba de informatică, cea mai importantă a concursului, candidații au de rezolvat următoarea problemă. Se dau n perechi de numere naturale și pentru fiecare pereche (x,y) trebuie să se afle câte numere naturale nenule strict mai mici decât produsul x * y sunt prime cu x * y.

#3227 Tramvaie C++

Timp de t zile Cebîșev a numărat in drum spre școală x mașini și y tramvaie. Se știe că numărul de tramvaie este egal cu numărul de numere mai mici sau egale cu x si prime cu acesta.

Știindu-se numărul de zile si numărul de mașini numărate în fiecare zi, calculați pentru fiecare zi numărul de tramvaie numărate de Cebîșev.

Se dau n numere naturale. Aflaţi pentru fiecare număr dat x, câte numere naturale nenule mai mici sau egale cu x sunt prime cu x?

#1908 Fractii_Ired C++

Dându-se şirul de fracţii 1/N, 2/N, 3/N, ...,N/N, să se afle câte fracţii sunt ireductibile.

Se consideră un șir de numere naturale mai mari decât 1, numere formate din cel mult 9 cifre. Să se scrie un program care determină dintre acestea numărul n pentru care raportul n/φ(n) are valoare maximă. În cazul în care sunt mai multe valori pentru care raportul n/φ(n) este maxim se va afișa prima dintre ele.

#2608 biprime

Se dă n un număr natural care este produsul a două numere prime distincte, şi m reprezentând numărul numerelor mai mici sau egale cu n, prime cu n. Aflaţi cele două numere prime din descompunerea lui n.

Se dă un număr natural n care este produs de trei numere prime distincte. Ştiind că există m numere naturale prime cu n şi mai mici decât acesta, să se afişeze în ordine crescătoare cele trei numere prime din descompunerea lui n.

Indicatorul lui Euler, φ(n) – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât n care sunt relativ prime cu n există. De exemplu, cum 1, 2, 4, 5, 7 și 8 sunt toate mai mici decât 9 și sunt relativ prime la 9, φ(9)=6. Numărul 1 e considerat a fi relativ prim cu toate numerele naturale, deci φ(1)=1. În mod interesant, φ(87109)=79180, și se poate observa că 87109 e o permutare a lui 79180.

Se consideră un șir de cel mult 10000 de numere naturale distincte mai mici decât 10.000.000. Să se scrie un program care găsește valoarea lui n, pentru care φ(n) e o permutare a lui n și fracția n/φ(n) are valoare minimă. Dacă sunt mai multe valori cu aceeași proprietate atunci se scrie prima valoare din șir. Dacă nu sunt valori cu proprietatea menționată se va scrie valoarea 0.

Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.

#2642 phi C++

Să se scrie funcția cu următorul antet:

int Phi(int n)

Funcția primește ca parametru un număr natural n și trebuie să returneze numărul de numere naturale nenule prime cu n și strict mai mici decât n.