오일러의 phi 함수 직접 구현해보면서 개념 익히기

정수론

오일러의 phi 함수 직접 구현해보면서 개념 익히기

1. 오일러의 phi 함수(Euler's phi function, totient function)

$\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다.

그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까

문제 풀면서 익히기로 하자

2. 구현 예시1 - 가장 간단한 구현

가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다.

그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다.

유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고,

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

2부터 n-1까지 n과 최대공약수를 구해보면서, 1이면 개수를 세준다.

1과는 어차피 서로소라서 최솟값이 1이고, n과는 어차피 서로소가 아니다.

#유클리드 호제법
def gcd(a,b):
    
    while b != 0:
        
        a,b = b, a%b
    
    return a

#오일러의 phi

def phi(n):
    
    #1과는 어차피 서로소이므로 최솟값은 1
    result = 1
    
    for i in range(2,n):
        
        if gcd(i,n) == 1: #2부터 n-1까지 n과의 최대공약수가 1이면
            
            result += 1
    
    return result

맞았는지 검증 해봐야겠지?

"""
phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
phi(8) = 4
phi(9) = 6
phi(10) = 4
"""

for i in range(1,11):
    
    print(phi(i))

"""
1
1
2
2
4
2
6
4
6
4
"""

시간복잡도는 $O(N^{2})$인줄 알았는데.. O(NlogN)이라고 하네?.. 아무튼

gcd가 O(N)번 수행인데... gcd 내부가 O(logN)인가.. 나머지 연산이니까?

3. 최적화하기1 - 오일러 phi함수의 성질을 이용

오일러의 phi 함수는 다음과 같은 성질을 가진다고 한다.

3-1) 첫번째 성질

간단하게 n이 소수라고 생각해보자. 그러니까 n이 소수일때, $\varphi(n)$의 값은 어떻게 구할까?

정의에 따라 1부터 n이하의 자연수 중에서 n과 서로소인 것의 개수이다.

그런데 소수 n은 1과 n만을 약수로 가지는 수이다.

그러므로 1~n-1까지는 모두 소수 n과 최대공약수가 1인 서로소이다.

따라서 n이 소수이면, 특별히 $\varphi(n) = n-1$이다.

3-2) 두번째 성질

정리1) 정수론의 기본정리(the fundamental theorem of arithmetic)

모든 양의 정수 n은 유일한 소인수 분해를 가진다.

즉, $n > 1$이면, $$n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}$$을 만족시키는 $p_{1} < p_{2} < ... < p_{r}$이고 각각은 소수이며, $k \geq 1$이 유일하게 존재한다.

그러면 n을 소인수분해 했을때, 각각의 소인수 구성이 $p_{1} < p_{2} < ... < p_{r}$이라면,

$\varphi(n)$은 다음과 같이 표현할 수 있다고 한다.

$$\varphi(n) = \prod_{i=1}^{r}n(1-\frac{1}{p_{i}})$$

이걸 할려면 결국 소인수분해를 할 수 있어야겠다.

-----------------------------------------------------------------------------------

소인수분해 기본 알고리즘 배우기 (tistory.com)

소인수분해 기본 알고리즘 배우기

1. 문제 11653번: 소인수분해 (acmicpc.net) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 소인수분해 하는 방법? 어렵게 생각할 필요 없이 사람이 소인수 분해를

deepdata.tistory.com

-----------------------------------------------------------------------------------

n을 소인수분해하기 위해, p = 2부터 시작해서, $p^{2} <= n$을 만족할때까지, 반복문을 수행

#소인수분해를 이용한 오일러 phi

def phi(n):
    
    #소인수 p1,p2,...,pr에 대하여,
    #n에 1-(1/p1), (1-(1/p2),..를 곱해나갈것이다.
    
    result = n 
    
    p = 2
    
    #소인수분해 시작
    while p*p <= n:

n이 p로 나누어 떨어진다면.. p는 n의 소인수이고 n을 p로 나눈 몫으로 n을 갱신

그런데

$$\varphi(n) = \prod_{i=1}^{r}n(1-\frac{1}{p_{i}})$$ 공식을 자세히 보면

소인수 $p_{i}$의 지수는 중요하지 않다.

그러니까 n이 $p_{i}$를 여러개를 가지고 있더라도 1개를 가진 것과 동일하다

그래서 조금 다르게, n이 p로 나누어 떨어진다면, p가 n의 소인수인 것은 맞는데...

n을 p로 나눈 몫으로 갱신하는 과정에서, n을 p로 나눈 몫이 다시 p로 나누어 떨어진다면, 계속 나눠서 몫으로 갱신해준다.

그러니까 나누어 떨어지지 않을때까지 계속 n을 p로 나눠서 갱신해준다.

#소인수분해를 이용한 오일러 phi

def phi(n):
    
    #소인수 p1,p2,...,pr에 대하여,
    #n에 1-(1/p1), (1-(1/p2),..를 곱해나갈것이다.
    
    result = n 
    
    p = 2
    
    #소인수분해 시작
    while p*p <= n:
        
        #n이 p로 나누어 떨어진다면.. p는 n의 소인수
        
        if n % p == 0:
            
            #n을 p로 나눈 몫으로 갱신하는데,
            #어차피 다음에도 n이 p로 나누어지는지 검사할거니까,
            #n이 p로 나누어 떨어지지 않을때까지 계속 반복해준다.
            
            while n % p == 0:
                
                n = n//p #n이 p로 나누어 떨어지면, n을 p로 나눈 몫으로 갱신

n이 p로 나누어 떨어져서, 몫으로 갱신하는 반복문을 수행하다가 n이 p로 나누어 떨어지지 않는다면,

p는 소인수이므로, result에 (1-(1/p))를 곱해준다.

#소인수분해를 이용한 오일러 phi

def phi(n):
    
    #소인수 p1,p2,...,pr에 대하여,
    #n에 1-(1/p1), (1-(1/p2),..를 곱해나갈것이다.
    
    result = n 
    
    p = 2
    
    #소인수분해 시작
    while p*p <= n:
        
        #n이 p로 나누어 떨어진다면.. p는 n의 소인수
        
        if n % p == 0:
            
            #n을 p로 나눈 몫으로 갱신하는데,
            #어차피 다음에도 n이 p로 나누어지는지 검사할거니까,
            #n이 p로 나누어 떨어지지 않을때까지 계속 반복해준다.
            
            while n % p == 0:
                
                n = n//p #n이 p로 나누어 떨어지면, n을 p로 나눈 몫으로 갱신
            
            #p는 n의 소인수이므로
            result = result * (1.0 - (1.0/float(p)))

다음 소인수분해를 위해, p에 1을 증가시키고 반복문을 계속 진행

#소인수분해를 이용한 오일러 phi

def phi(n):
    
    #소인수 p1,p2,...,pr에 대하여,
    #n에 1-(1/p1), (1-(1/p2),..를 곱해나갈것이다.
    
    result = n 
    
    p = 2
    
    #소인수분해 시작
    while p*p <= n:
        
        #n이 p로 나누어 떨어진다면.. p는 n의 소인수
        
        if n % p == 0:
            
            #n을 p로 나눈 몫으로 갱신하는데,
            #어차피 다음에도 n이 p로 나누어지는지 검사할거니까,
            #n이 p로 나누어 떨어지지 않을때까지 계속 반복해준다.
            
            while n % p == 0:
                
                n = n//p #n이 p로 나누어 떨어지면, n을 p로 나눈 몫으로 갱신
            
            #p는 n의 소인수이므로
            result = result * (1.0 - (1.0/float(p)))
        
        p = p + 1

이제, 반복문을 탈출했는데도, n > 1이면 n은 그 자체로 소수이다.

그러니까 이 n도 원래 n의 소인수가 된다.

따라서 (1-(1/n))을 result에 곱해준다.

#소인수분해를 이용한 오일러 phi

def phi(n):
    
    #소인수 p1,p2,...,pr에 대하여,
    #n에 1-(1/p1), (1-(1/p2),..를 곱해나갈것이다.
    
    result = n 
    
    p = 2
    
    #소인수분해 시작
    while p*p <= n:
        
        #n이 p로 나누어 떨어진다면.. p는 n의 소인수
        
        if n % p == 0:
            
            #n을 p로 나눈 몫으로 갱신하는데,
            #어차피 다음에도 n이 p로 나누어지는지 검사할거니까,
            #n이 p로 나누어 떨어지지 않을때까지 계속 반복해준다.
            
            while n % p == 0:
                
                n = n//p #n이 p로 나누어 떨어지면, n을 p로 나눈 몫으로 갱신
            
            #p는 n의 소인수이므로
            result = result * (1.0 - (1.0/float(p)))
        
        p = p + 1
    
    
    #여기서 n이 1보다 크면 n은 소수이다.
    
    if n > 1:
        
        result = result * (1.0-(1.0/float(n)))
    
    return int(result) #result가 float이므로...

역시 실제로 맞는지 점검?

"""
Phi(1) = 1
Phi(2) = 1
Phi(3) = 2
Phi(4) = 2
Phi(5) = 4
Phi(6) = 2
Phi(7) = 6
Phi(8) = 4
Phi(9) = 6
Phi(10) = 4
"""
for i in range(1,11):
    
    print(phi(i))

"""
1
1
2
2
4
2
6
4
6
4
"""

이렇게 구하면 $O(\sqrt{n}logn)$이라고 함

반복문이 $p^{2} <= n$에만 수행하니까 그런듯

그런데.. 이 방법의 가장 큰 아쉬운점?은 float(p)를 계산하면서.. int()로 바꾸다보니까

오차가 생길수도 있다고 해야하나.. floating point 계산이 아쉽다

이걸 어떻게 피할 수 있을까?

4. 최적화하기2 - floating point 연산 피하기

사실, $$\varphi(n) = \prod_{i=1}^{r}n(1-\frac{1}{p_{i}})$$은... 어디서 나왔냐면..

$$n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}$$을 대입하면..

$$\varphi(n) = p_{1}^{k_{1}-1}(p_{1}-1)p_{2}^{k_{2}-1}(p_{2}-1)...p_{r}^{k_{r}-1}(p_{r}-1)$$

에서 나왔다.

두 식은 완전히 동일하다.

그래서 이를 이용하면 나눗셈 float point 연산을 수행하지 않고도 구할 수 있다.

어떻게 하냐면..

result = n으로 초기화한다.

n을 소인수분해를 하는데.. n의 첫번째 소인수를 찾으면.. 그것을 $p_{1}$이라고 하자.

그러면 result를 $p_{1}$으로 나눠준다.

$$result = n = p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}}$$이므로, $p_{1}$으로 나누면?

$$p_{1}^{k_{1}-1}p_{2}^{k_{2}}...p_{r}^{k_{r}}$$이 된다.

두 식을 빼면 어떻게 될까?

$$p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{r}^{k_{r}} - p_{1}^{k_{1}-1}p_{2}^{k_{2}}...p_{r}^{k_{r}}$$

인데, $$p_{2}^{k_{2}}...p_{r}^{k_{r}}$$으로 묶을수있다.

$$(p_{1}^{k_{1}} - p_{1}^{k_{1}-1})p_{2}^{k_{2}}...p_{r}^{k_{r}}$$

그러면..?

$$p_{1}^{k_{1}-1}(p_{1} - 1)p_{2}^{k_{2}}...p_{r}^{k_{r}}$$

만약에, 모든 소인수 $p_{1}, p_{2}, ..., p_{r}$에 대해 위 과정을 반복한다면?

$$\varphi(n) = p_{1}^{k_{1}-1}(p_{1}-1)p_{2}^{k_{2}-1}(p_{2}-1)...p_{r}^{k_{r}-1}(p_{r}-1)$$을 얻을 수 있을 것이다.

그러므로 알고리즘은 다음과 같다.

4-1) result = n으로 초기화한다.

4-2) p = 2부터 시작해서, p*p <= n일때까지 소인수분해 4-3),4-4) 반복문을 수행

4-3) n이 p로 나누어 떨어진다면, 다음을 반복

n을 p로 나눈 몫으로 n을 갱신한다.

n이 p로 나누어 떨어지지 않는다면 반복문을 탈출

4-4) 반복문을 탈출한다면, result에서 result를 p로 나눈 몫을 뺀 값을 result로 갱신

4-5) n이 p로 나누어 떨어지지 않으면, p에 1 증가

4-6) 위 반복문을 수행하지 않았는데, n > 1이면, n은 그 자체로 소수이므로, result를 n으로 나눈 몫을 result에 빼준다.

#소인수분해를 이용한 개선된 오일러 phi함수

def phi(n):
    
    #result = n으로 초기화
    
    result = n 
    
    #n에 대한 소인수분해 시작
    #p=2부터 시작
    
    p = 2
    
    #p*p <= n일때, 소인수분해 반복문을 수행
    
    while p*p <= n:
        
        #만약 n이 p로 나누어 떨어진다면?
        #p는 n의 소인수이다.
        
        if n % p == 0:
            
            #n이 p로 나누어 떨어진다면
            #n을 p로 나눈 몫으로 n을 갱신하는 과정을 반복
            
            while n % p == 0:
                
                n = n//p
            
            #반복문을 탈출하면, p는 n의 소인수이고
            #다음 소인수를 찾을 차례인데, 그 전에 result값을 갱신
            
            #result에서 result를 p로 나눈 몫을 빼준다.
            
            #아래 둘은 동일한 식
            
            result -= result//p
            #result = result // p * (p - 1)
        
        #n이 p로 나누어 떨어지지 않으면
        #p에 1 증가
        p = p + 1
    
    #반복문 밖에서 n이 1보다 크다면, n은 그 자체로 소수이다.
    if n > 1:
        
        result -= result//n
    
    return result

연습문제는 아까우니까 내일 해보고 맞게 구현했는지 점검해보자

"""
Phi(1) = 1
Phi(2) = 1
Phi(3) = 2
Phi(4) = 2
Phi(5) = 4
Phi(6) = 2
Phi(7) = 6
Phi(8) = 4
Phi(9) = 6
Phi(10) = 4
"""

for i in range(1,11):
    
    print(phi(i))

"""
1
1
2
2
4
2
6
4
6
4
"""

5. 연습문제

11689번: GCD(n, k) = 1 (acmicpc.net)

11689번: GCD(n, k) = 1

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

오일러 phi함수를 구현하면 되는 문제

6. 풀이

기본 알고리즘으로는 n이 10^12이다 보니 1초안에 못풀고

최적화된 알고리즘을 사용해야한다.

$\varphi(n) = \prod_{i=1}^{r}n(1-\frac{1}{p_{i}})$에 의한 알고리즘1

from sys import stdin

def phi(n):
    
    result = n
    
    p = 2
    
    while p*p <= n:
        
        if n % p == 0:
            
            while n % p ==0:
                
                n = n//p
            
            result = result * (1.0-(1.0/float(p)))
        
        p = p + 1
    
    if n > 1:
        
        result = result * (1.0-(1.0/float(n)))
        
    return int(result)

n = int(stdin.readline())

print(phi(n))

$\varphi(n) = p_{1}^{k_{1}-1}(p_{1}-1)p_{2}^{k_{2}-1}(p_{2}-1)...p_{r}^{k_{r}-1}(p_{r}-1)$에 의한 알고리즘2

from sys import stdin

n = int(stdin.readline())

result = n

p = 2

while p*p <= n:
    
    if n % p == 0:
        
        while n % p == 0:
            
            n = n//p
        
        result -= result//p
    
    p = p + 1

if n > 1:
    
    result -= result//n

print(result)

참조

Euler's Totient Function - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Euler's totient function - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search Number of integers coprime to and not exceeding n "φ(n)" redirects here. For other uses, see Phi. The first thousand values of φ(n). The points on the top line represent φ(p) when p

en.wikipedia.org

알고리즘 - 소인수 분해 (velog.io)

알고리즘 - 소인수 분해

소인수 분해

velog.io

코드노예 :: 오일러 피 함수 (tistory.com)

오일러 피 함수

소수 계산과 함께 많이 쓰이는 오일러 피 함수 입니다. 피 함수는 자신보다 작은 양수 중에서 자기 자신과의 최대 공약수가 1인 숫자가 몇 개인지를 나타냅니다. 따라서 소수 p의 경우 모든 숫자

codenoyes.tistory.com

오일러 피 함수 - 나무위키 (namu.wiki)

오일러 피 함수 - 나무위키

namu.wiki

'정수론' 카테고리의 다른 글

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기 (0)	2022.12.16
페르마의 소정리 문제 풀어보면서 익히기 (0)	2022.12.15
소인수분해 기본 알고리즘 배우기 (0)	2022.12.13
정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? - (0)	2022.09.09
소수를 빠르게 구하는 에라토스테네스의 체 알고리즘 (0)	2022.09.07

TAGS.

통계학 세상

통계학 세상

통계학 세상