252
Cerința
Dându-se şirul de fracţii 1/N, 2/N, 3/N, ...,N/N
, să se afle câte fracţii sunt ireductibile.
Date de intrare
Programul citește de la tastatură numărul N
.
Date de ieșire
Programul va afișa pe ecran numărul de fracţii ireductibile.
Restricții și precizări
1 ≤ n ≤ 2.000.000.022
Exemplu
Intrare
4
Ieșire
2
Explicație
Fracţiile sunt 1/4, 3/4
.
#include <bits/stdc++.h> using namespace std; int main() { long long int n , d = 2; cin >> n; long long int nr = n; while(n > 1) { if(n % d == 0) { nr /= d; nr *= d - 1; while(n % d == 0) n /= d; } if(d == 2) d = 3; else d += 2; if(d * d > n) d = n; } cout << nr; return 0; }
Comentarii