알고리즘 스터디 7일차

목차

1. 소수 구하기

2. 오일러피

3. 유클리드 호제법

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 소수 구하기

소수 : 1과 자기 자신 외에 약수가 존재하지 않는 수

에라토스테네스의 체 원리

시간 복잡도 : O(Nlog(logN)) : 이중 for문을 사용하지만 바깥쪽 for문을 생략하는 경우 

 

1~30에서 에라토스테네스의 체 원리를 통해 소수 구하기

 1) 1은 소수가 아니므로 삭제, 2를 선택하고 2의 배수 전부 삭제 (2는 삭제안함)

 2) 그 다음 숫자인 3을 선택하고 3의 배수 전부 삭제, 4는 1)에서 삭제했으므로 5를 선택, 같은 과정 반복

 3) 삭제되지 않은 수를 모두 출력 (2,3,5,7,11,13,17,19,23,29 => 소수)

 

2. 오일러피

P[N] : 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

서로소 : 공약수가 1이외에 없는 수

 

P[6] =  2 (1,2,3,4,5,6 에서 6과 서로소인 자연수는 1,5 이다.)

 

위 그림과 같은 과정을 통해 나온 배열이 오일러피 함수이다. (P[1] = 1, P[2] = 1, ... , P[15] = 8)

서로소 문제를 만났을 때 오일러피를 모른다면 어떻게 푸는지 감도 잡히지 않아 기억하는 것이 중요하다.

 

3. 유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

MOD연산 : 두 값을 나눈 나머지를 구하는 연산 (10 MOD 4 = 2 : 10 % 4 =2 와 같다)

 

다음 3가지 단계를 통해 유클리드 호제법을 구현할 수 있다.

1) 큰 수를 작은 수로 나누는 MOD 연산을 수행

2) 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행

3) 단계 2)를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

 

270,192 의 최대공약수를 유클리드 호제법으로 찾는 그림