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.
Restricții și precizări
2 ≤ n ≤ 2.000.000.000
Numele funcției este Phi.
Spunem că un număr natural x este prim cu n dacă cmmdc(x, n) = 1.
Eu am rezolvat problema in mai multe moduri, insa depaseste limita de timp la unele probe de fiecare data si nu stiu cum sa o mai abordez.
40
Aici e una dintre rezolvarile mele: int Phi (int n){
int x=1,aux,aux2,i,nr=0;
aux = n;
for (i=1;i<=n-1;i++){
aux2 = x;
while (x!=n)
if (x>n)
x=x-n;
else
n=n-x;
if (n==1)
nr++;
x = aux2;
x++;
n = aux;
}
return nr;
}
int x=1,aux,aux2,i,nr=0;
aux = n;
for (i=1;i<=n-1;i++){
aux2 = x;
while (x!=n)
if (x>n)
x=x-n;
else
n=n-x;
if (n==1)
nr++;
x = aux2;
x++;
n = aux;
}
return nr;
}
Am mai incercat calculand cmmdc-ul recursiv, intr-o functie separata, dar tot 40 de puncte faceam, asa ca am presupus ca trebuie calculat in interiorul functiei Phi, dar tot 40 de puncte fac:))
mai medităm....
Răspunsuri la întrebare
Răspuns de
2
#include <iostream>
#include <algorithm>
int Phi(int n)
{
// forma recursiva este ineficienta
int result = 1;
for (int i = 2; i < n; ++i)
if(std::__gcd(i, n) == 1)
++result;
return result;
}
Alte întrebări interesante
Matematică,
8 ani în urmă
Matematică,
8 ani în urmă
Matematică,
8 ani în urmă
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Limiya memorie 2 MB / 1 MB, deacee tr. de găsit ceva „deștept”... :)))