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

#18 소수 구하기

M이상 N이하의 자연수 중 소수 모두 출력

최대 크기 1,000,000이므로 시간복잡도가 O(N^2)인 알고리즘은 사용 불가하다.

 

과정

1. 크기가 N+1인 배열 생성, 각 요소에 인덱스 대입 // 인덱스 순서 1부터 시작하여 신경 안 쓰게 하기 위하여

2. 1은 소수 X이므로 삭제, 2부터 N의 제곱근까지 탐색하여 값이 인덱스와 일치하면 그대로 두고

// 처음 선택한 수는 소수로 인정, 그 배수는 삭제

3. 남아 있는 수 모두 출력 // M이상 N이하

 

*N의 제곱근까지만 탐색하는 이유

N을 두 수의 곱 a*b로 표현하면 각 수인 a, b는 둘중 하나는 N의 제곱근보다 클 수 없다.

그러므로 N의 제곱근까지만 탐색하면 전체 범위의 소수 탐색 가능

 

for(int i = 2; i <= Math.sqrt(N); i++) // N의 제곱근까지 반복

if(A[i] == 0) continue; // 이미 소수가 아니라고 판정 되었으면 넘어감

 

for(int j = i+i; j<=N; j=j+i) { // 현재 선택된 수의 배수 삭제, 인덱스 주의

A[j] = 0;

 

for(int i =M; i<=N; i++) { // 범위 M부터 N까지

if(A[i] != 0) // 소수라고 판정 되었으면

System.out.println(A[i]);

}

 

#19 최소 공배수 구하기

최소 공배수란? 두 수의 공배수 중에서 최솟값

 

코딩 테스트에서 최소 공배수 구하는 법 a*b/최대공약수

 

수학적으로 최소 공배수 구하는 법

2 36 48

2 18 24

3 9 12

  3 4 // 서로소가 될때까지 소수로 나누고 모두 곱한다.

2*2*3*3*4 == 144 // 최소 공배수

 

두 수의 곱은 최대 공약수가 1번 중복 되어 있으므로 두 수의 곱에서 최대 공약수를 나누어 빼주면 최소 공배수가 된다.

 

유클리드 호제법은 재귀함수로 구현한다.

 

result = a*b / gcd(a,b);

 

gcd(a, b)

if(b==0)

return a;

else{

return gcd(b, a%b);

 

// 항상 맨 앞에 큰수가 전달되지 않지만, 나머지 연산 떄문에 자연스럽게 swap 된다.