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.

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

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema maxprimeintreele:

#include <bits/stdc++.h>
using namespace std;
int Euler(int x)
{
    int d,e=x;
    if(x%2==0)
    {
        e=e-e/2;
        while(x%2==0)
            x/=2;
    }
    for(d=3; d*d<=x; d=d+2)
        if(x%d==0)
        {
            e=e-e/d;
            while(x%d==0)
                x/=d;
        }
    if(x>1)
        e=e-e/x;
    return e;
}
int main()
{
    ifstream f("maxprimeintreele.in");
    ofstream g("maxprimeintreele.out");
    int x,y;
    float maxi=0,z;
    while(f>>x)
    {
        z=(float)x/Euler(x);
        if(z>maxi)
        {
            maxi=z;
            y=x;
        }
    }
    g<<y;
    f.close();
    g.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3289 maxprimeintreele

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3289 maxprimeintreele de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3289 maxprimeintreele