Question

Se consideră un număr natural n. Să se realizeze un program pentru determinarea numărului perechilor (a,b) de numere naturale (a,b <=n) ce au proprietatea că a şi b sunt prime între ele

Answer 1

Explicație:

Daca (a,b) si (b, a) sunt perechi identice:

$\displaystyle\textrm{numarul de perechi} = \sum_{b=1}^n\phi(b)$

#include <iostream>

using namespace std;

int indEuler(int x){

int ind = 1, d;

for(d = 2; x != 1; d++){

if(x%d==0){

ind *= (d-1);

x /= d;

while(x%d==0) ind *= d, x /= d;

}

d += (d%2);

}

return ind;

}

int main(){

int n, total = 0;

cin >> n;

for(int b = 1; b <= n; b++){

total += indEuler(b);

}

cout << total;

}

Daca (a,b) si (b,a) sunt perechi diferite, trebuie doar sa dublam rezultatul si sa scadem 1( de la perechea (1,1) ):

#include <iostream>

using namespace std;

int indEuler(int x){

int ind = 1, d;

for(d = 2; x != 1; d++){

if(x%d==0){

ind *= (d-1);

x /= d;

while(x%d==0) ind *= d, x /= d;

}

d += (d%2);

}

return ind;

}

int main(){

int n, total = 0;

cin >> n;

for(int b = 1; b <= n; b++){

total += indEuler(b);

}

total = total * 2 - 1;

cout << total;

}