# PBinfo #3289 – maxprimeintreele – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerința
Indicatorul lui Euler, φ(n) – uneori numită funcția phi, este folosit pentru a determina câte numere mai mici decât n sunt relativ prime cu n. De exemplu, cum 1, 2, 4, 5, 7 și 8 sunt toate mai mici decât 9 și relativ prime la 9, φ(9)=6.


nRelativ primeφ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666….
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

Se poate vedea că n=6 produce valoarea maximă n/φ(n) pentru n ≤ 10.

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.

Date de intrare
Fișierul de intrare maxprimeintreele.in conține pe prima linie cel mult 10000 numere naturale din intervalul [2,999999999] separate prin spații.

Date de ieșire
Fișierul de ieșire maxprimeintreele.out va conține pe prima linie numărul k, reprezentând numărul n pentru care raportul n/φ(n) are valoare maximă.

Restricții și precizări

numerele din fișierul de intrare sunt din intervalul [2, 999999999]

Exemplu:
maxprimeintreele.in

2 3 4 5 6 7 8 9 10
maxprimeintreele.out

6
Explicație
Dintre numerele aflate în fișierul de intrare, numărul 6  are raportul n/φ(n) cu valoare maximă și anume 3.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
string problema = "maxprimeintreele";
ifstream in(problema + ".in");
ofstream out(problema + ".out");
#define cin in
#define cout out
int phi(int x) {
    int d, e = x;
    if (x % 2 == 0) {
        e = e - e / 2;
        while (x % 2 == 0) x = x /2;
    } for (int d = 3; d * d <= x; d = d + 2)
        if (x % d == 0) {
            e = e - e / d;
            while (x % d == 0) x = x / d;
    } if (x > 1) e = e - e / x;
    return e;
} int main() {
    int x, y;
    float maxim = 0;
    while (cin >> x) {
        float temp = (float)x / phi(x);
        if (temp > maxim) {
            maxim = temp;
            y = x;
        }
    } cout << y;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3289)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3289/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3289/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)