[정수론] 오일러 피(phi) - 정수 N까지 서로소의 개수

 

 

서로소란?
공약수가 1외에 없는 수를 뜻함

공약수란?
둘 이상의 정수에서 공통된 약수를 뜻함

공약수와 연관지어 설명하자면
서로소란 둘 이상의 정수에서 공통된 약수중 공약수가 1 외에 없는 수를 말한다.

ex) 28과 45은 서로소이다. => 공약수가 1밖에 없기 때문 (두 수는 공통분모, 연관성이 1외에는 없다)

 

오일러 피(phi)

오일러 피 함수 P[N]의 정의는  1부터 N 까지 범위에서 N과 서로소인 자연수의 갯수를 뜻한다.

ex) P[6] = 1~6 범위에서 6과 서로소인 자연수의 갯수

     {1, 2, 3, 4, 5, 6} => {1, 5} 2개

 

<핵심 이론>

에라토스테네스 - 체 이론과 비슷하다.

1. 구하고자 하는 오일러 피의 범위 만큼 배열을 자기 자신 인덱스값으로 초기화
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (=소수일 때) 현재 선택한 숫자 (k)의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i] / k 연산을 수행 (i는 k의 배수)
3. 배열의 끝까지 2. 를 반복하여 오일러 피 함수 완성

<핵심 원리>

 

1. 구하고자 하는 범위까지 배열 생성 후 2를 선택

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

start index : 2

 

2. 선택한 수 2의 배수마다 P[i] = P[i] - P[i] / 2 연산을 수행해 값을 갱신

ex) 8 = 8 - 8/2 = 4

 

 

{2, 4, 6, 8, 10, 12, 14}

• P[2] = 2 - 2 / 2 = 1
• P[4] = 4 - 4 / 2 = 2
• P[6] = 6 - 6 / 2 = 3
• P[8] = 8 - 8 / 2 = 4
• P[10] = 10 - 10 / 2 = 5
• P[12] = 12 - 12 / 2 = 6
• P[14] = 14 - 14 / 2 = 7

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15

 

위와 같이 소수 구하기에서 배수를 지우는 부분만 P[i] = P[i] - P[i] / k 로 변경하면 오일러피 함수를 간단하게 구현할 수 있다.

단, N = ∮(N)인 곳(소수)만을 찾아  값 갱신 해야한다.

 

3. 탐색 계속 진행

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15

이전 선택 값 2  다음 수 3이 3 = ∮(3) 이므로 3 선택

 

 

start index : 3

{3, 6, 9, 12, 15} → {3, 3, 9, 6, 15}

• P[3] = 3 - 3 / 3 = 2
• P[6] = 3 - 3 / 3 = 2
• P[9] = 9 - 9 / 3 = 6
• P[12] = 6 - 6 / 3 = 4
• P[15] = 15 - 15 / 3 = 10

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10

 

4. 배열이 끝날때 까지 반복 (인덱스와 같은 수가 없을 때 == 더 이상 선택할 수가 없을 때)

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10

이전 선택 값 3 다음 수 4는 4 ≠ ∮(4) 다음 수 5 확인 5 = ∮(5)  이므로 5 선택

 

 

start index : 5

{5, 10, 15} → {5, 5, 10}

• P[5] = 5 - 5 / 5 = 4
• P[10] = 5 - 5 / 5 = 4
• P[15] = 10 -10 / 5 = 8

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10
∮(5)	1	1	2	2	4	2	7	4	6	4	11	4	13	7	8

 

 

start index : 7

{7, 14} → {7, 7}

• P[7] = 7 - 7 / 7 = 6
• P[14] = 7 - 7 / 7 = 6

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10
∮(5)	1	1	2	2	4	2	7	4	6	4	11	4	13	7	8
∮(7)	1	1	2	2	4	2	6	4	6	4	11	4	13	6	8

 

 

start index : 11

{11}

• P[11] = 11 - 11 / 11 = 10

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10
∮(5)	1	1	2	2	4	2	7	4	6	4	11	4	13	7	8
∮(7)	1	1	2	2	4	2	6	4	6	4	11	4	13	6	8
∮(11)	1	1	2	2	4	2	6	4	6	4	10	4	13	6	8

 

 

start index : 13

{13}

• P[13] = 13 - 13 / 13 = 12

15	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
∮(2)	1	1	3	2	5	3	7	4	9	5	11	6	13	7	15
∮(3)	1	1	2	2	5	2	7	4	6	5	11	4	13	7	10
∮(5)	1	1	2	2	4	2	7	4	6	4	11	4	13	7	8
∮(7)	1	1	2	2	4	2	6	4	6	4	11	4	13	6	8
∮(11)	1	1	2	2	4	2	6	4	6	4	10	4	13	6	8
∮(13)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8

 

수학적 측면

ex) N = 6 일때 

• 초기 상태 ∮(6) = 6  → 서로소가 될 수 있는 후보의 갯수로 초기화한다.
  →  1~6 범위 자연수 그 자체 (1, 2, 3, 4, 5, 6)
  ex) N = 6일때 P[6] = 1~6 범위의 서로소 갯수
• 2의 배수로 인한 탈락 →  6 - 6 / 2 = 3 {1, 3, 5} ← 2의 배수 제거 (1, 2, 3, 4, 5, 6)
• 3의 배수로 인한 탈락 → 3 - 3 / 3 = 2 {1, 5} ← 3의 배수 제거 (1, 3, 5)

6값이 3으로 변한 의미는 3의 배수 중에서 6이 2의 배수로 인해 탈락했다느 것을 의미,

다시말해 6은 3과 2의 공배수 이므로 2로도 삭제가가능하고 3으로도 삭제가 가능하기 때문에 중복 삭제를 막기 위함