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.

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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("maxprimeintreele.in");
ofstream cout("maxprimeintreele.out");

double maxi = 0;
int nrmaxi;

long Totient(long nr)
{
  long i,rank = nr;
  if(nr==1) return 0;
  if (!(nr%2))
   {
         rank -= rank/2;
         while(!(nr%2)) nr /= 2;
   }
  for (i = 3; i*i <= nr; i += 2)
   if (!(nr%i))
        {
          rank -= rank/i;
          while (!(nr%i)) nr /= i;
        }
  if (nr>1) rank -= rank/nr;
  return rank;
}

int main(){
    int x;
    while(cin >> x){
        if((double) x / Totient(x) > maxi)
            maxi = (double) x / Totient(x), nrmaxi = x;
    }
    cout << nrmaxi;
    return 0;
}