The Euler's totient

Author

vinay_e

3000

The Euler's totient of a positive integer n is the number of positive integers not greater than n that are relatively prime to n (i.e. their greatest common divisor equals 1).
In this challenge, your task is to write a function that computes the Euler's totient of a given number.

Example

• eulersTotient(2) = 1
1 is the only number relatively prime to 2.
• eulersTotient(1) = 1
1 is the only number relatively prime to 1.
• eulersTotient(10) = 4
  The following numbers are relatively prime to 10: 1, 3, 7 and 9.

• [input] integer n

  A positive integer, 1 ≤ n < 109.

• [output] integer

  Euler's totient of n.

- from CodeFights

( https://codefights.com/challenge/iDrZXiemeR8BFYMgZ )

The Euler's totient (오일러 피 함수)

n이 주어졌을때 1부터 n까지의 양의 정수 중, n과 서로소인 정수의 갯수를 나타내는 함수.

예를 들어, n = 1 일 땐 f(n) = 1

n = 10 일 땐 f(n) = 4

( 10과 서로소인 정수는 1, 3, 7, 9) 

다음은 내가 처음으로 시도한 코드다.

빠르게 3분안에 '우왕 개쉽네 거저문제당ㅋ' 하면서 풀었겄만..

time limit exceed..

혹시 while 문을 작성할 때 무한루프에 빠지지 않나 싶어서 꼼꼼히 생각했지만 while문 흐름 자체엔 별 문제가 없었다.

문제는 코드의 효율성

혹시나 해서 같은 코드 그대로 다른 컴파일러로 돌려보니

n이 1000 을 넘어서부터 러닝 타임이 초 단위 이상으로 소요되는 것이다.

1에서부터 n까지 모든 정수를 하나하나씩 각각 비교해 GCD를 구하면서 검사를 하고 앉아있으니..

비효율적이고, 시간이 오래 걸릴 수 밖에 없는 것이다.

1. GCD 를 n번 구하고,

2. GCD를 유클리드 알고리즘으로 계산할 때 1에서 n까지 존재할 수 있는 최대 자릿수는 Log10n

그러므로 시간 복잡도는 O(nlogn)이다.

조금 더 효율적인 다른 방법을 찾아보자.

참조

http://www.geeksforgeeks.org/eulers-totient-function/ (오일러 피함수)

http://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm   (유클리드 알고리즘 시간 복잡도)