Pb Info #3289
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.
n Relativ prime φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666….
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.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.
Răspunsuri la întrebare
Răspuns:
#include <fstream>
using namespace std;
ifstream in("maxprimeintreele.in");
ofstraem out("maxprimeintreele.out");
long long phi (long long n)
{
long long d=2, e=n;
while(d*d<=n)
{
if(n%d==0)
{
e=e/d*(d-1);
while(n%d==0)
{
n/ =d;
}
}
d++;
}
if(n!=1)
{
e=e/n*(n-1);
}
return e;
}
int main()
{
long long x, maxx;
float maxi=0, k;
while(in>>x)
{
k=(float)x/phi(x);
if(k>maxi)
{
maxi=k;
maxx=x;
}
}
out<<maxx;
return 0;
}