[알고리즘] 오일러 피 함수

1. 개념

1과 n까지의 수 중에서 n과 서로소인 수의 개수를 찾는 함수. 예를 들어 8을 오일러 피 함수에 넣어 값을 구하면 4가 나온다. 8과 서로소인 수는 1, 3, 5, 7이기 때문이다.

 

*서로소

두 수의 공약수가 1뿐인 수.

 

2. 방법

• 구하고자 하는 범위만큼 배열을 초기화한다.
• 2부터 시작해서 현재 선택된 숫자(2)의 배수에 해당하는 수를 탐색하면서 그 수를 수-수/2 로 업데이트한다.
• 그 다음 소수로 넘어가서 위 과정을 반복한다.

 

3. 원리

1) 소수의 배수/소수의 의미

소수의 배수/소수를 하면 소수의 배수보다 작은 수 중 소수를 무조건 약수로 가져서 소수의 배수와 서로소가 될 수 없는 수들의 개수를 구할 수 있다.

2) 수-수/2

결국 수에서 위에서 구한 걸 빼주면 수보다 작거나 같은 수 중 서로소가 절대 될 수 없는 수의 개수를 제거할 수 있다.

1과 2에 따라 이를 소수의 배수에 해주면 해당 수보다 작거나 같은 수 중 서로소가 될 수 있는 수의 개수를 구할 수 있다.

 

* 소수만 가지고 하는 이유는, 소수의 배수를 다 돌아서 제거를 해 주면 한 번씩 다 돌 수 있기 때문이다. 예를 들어 3이 소수라 3의 배수를 싹 돌았다고 하자. 그런데 6을 만나고 6을 또 돌면 중복해서 제거될 수가 있다. 그래서 소수만 돌아야 한다.

 

4. 관련 문제

백준 11689

 

 

*사실 이 개념에 대해 잘 이해가 안 간다...