-
Notifications
You must be signed in to change notification settings - Fork 1
/
EULER_PH.cpp
executable file
·55 lines (41 loc) · 916 Bytes
/
EULER_PH.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cmath>
#define FOR(i,a,b) for(int i = a ; i < b ; ++i )
using namespace std;
int PHI( int n );
int main(){
int t, n, k, a, b;
ios_base::sync_with_stdio( false );
cin >> t;
FOR( i , 0 , t ){
cin >> n ;
cout << PHI( n ) << endl;
}
return 0 ;
}
//*****************************************************************************
int PHI( int n ){
if( n == 1 )
return 0;
int dzielnik = 2, potega = 1, i = 3, s = sqrt( n );
if( n % 2 != 0 ){
dzielnik = -1;
while( i <= s and dzielnik == -1 ){
if( n % i == 0 )
dzielnik = i;
i++;
}
}
if (dzielnik == -1 ){
return n-1 ;
}
int temp = dzielnik ;
while( n % (dzielnik * temp) == 0){
dzielnik *= temp;
potega ++;
}
if( dzielnik == n )
return (temp-1)*(n/temp);
return PHI( dzielnik ) * PHI( n/dzielnik );
}
//*****************************************************************************