Do it 알고리즘 코딩테스트 하루코딩 7장 정수론 이론

#18 소수 구하기(에라토스테네스의 체)

소수(prime number)? 약수가 1과 자기 자신 이외에는 존재하지 않는 수

// 1은 소수가 아니다.

 

코딩테스트에서는 에라토스테네스의 체를 사용하여 소수를 구한다.

 

과정

1. 구하고자하는 범위 만큼 1차원 배열 생성

2. 2부터 시작하여 // 1은 소수가 아니므로 삭제

배열에서 현재 선택된 숫자의 배수에 해당하는 수를 끝까지 탐색하며 삭제

처음 선택된 숫자는 지우지 않는다. // 소수이므로

3. 끝까지 과정 2를 반복후 남아 있는 수를 출력 // 소수

 

시간복잡도는?

이중 for문 이므로 O(n^2) 이라고 생각하지만 아니다. 실제는 O(nlog(logn)) // 바깥 for문이 빈번하게 생략되므로

 

# 19 최대 공약수 구하기(유클리드 호제법)

최대 공약수란? 두 수의 공통된 약수 중에서 최대 값

소인수분해해서 공통된 소수의 곱으로 표현 // 학창시절에 수학

 

코딩테스트에서는 유클리드 호제법을 사용하여 최대 공약수를 구한다. // MOD 연산 즉, 나머지 연산 % 사용

 

과정

1. 큰 수를 작은 수로 나눈 나머지를 구하는 나머지 연산 수행

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

3. 과정 2를 반복하다가 나머지가 0이 되는 순간의 작은 수가 최대 공약수이다.

 

재귀함수로 구현