FilesExpand file tree

 master

/

EulersFunction.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

27 lines (25 loc) · 744 Bytes

 master

/

EulersFunction.java

Top

File metadata and controls

• Code
• Blame

27 lines (25 loc) · 744 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package Others;

/**

* You can read more about Euler's totient function

* <p>

* See https://en.wikipedia.org/wiki/Euler%27s_totient_function

*/

public class EulersFunction {

// This method returns us number of x that (x < n) and gcd(x, n) == 1 in O(sqrt(n)) time complexity;

public static int getEuler(int n) {

int result = n;

for (int i = 2; i * i <= n; i++) {

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

}

if (n > 1) result -= result / n;

return result;

}

public static void main(String[] args) {

for (int i = 1; i < 100; i++) {

System.out.println(getEuler(i));

}

}

}