[Algorithm-PS] 가장 작은 약수

 

a와 b를 포함하여 사이에 있는 정수의 약수를 모두 구하여

가장 많이 나온 약수를 구하는 문제가 있다.

만약 많이 나온 약수의 개수가 여러 개 존재한다면, 가장 작은 약수를 구해야 한다. (약수가 1인 것은 제외)

(단, 2 <= a, b <= 10^9)

 

해당 문제는 범위를 잘 보며 문제를 풀어야 한다.

처음에는 범위 생각않고 풀었다가 시간 초과를 맞닥뜨렸다.

 

그냥 정말로 a와 b를 포함한 사잇수의 약수의 빈도수를 구하면

시간 초과가 나올 수밖에 없다.

 

그러면 한번 수학적으로 생각해보자,

가장 빈도 수가 높으면서 작은 약수는 무엇일까?

당연히 2가 아닐까? (모든 짝수는 약수로 2를 갖고 있으므로~.~)

 

a가 12이고 b가 15라고 가정해보자.

12의 약수 - 1, 2, 3, 4, 6, 12

13의 약수 - 1, 13

14의 약수 - 1, 2, 7, 14

15의 약수 - 1, 3, 5, 15

 

자, 여기서 1을 제외한 약수 중 가장 빈도수가 높은 약수는?

2번씩 나온 2와 3이다.

그렇다면 여기서 제일 작은 약수는?

바로 2이다.

 

그렇다는 건, a와 b가 같은 경우가 아니라면, 가장 빈도수가 높으면서 가장 작은 약수는

2라는 결과'밖에' 나올 수 없다.

 

그럼 a와 b가 같으면요?

같으면, 해당 수의 약수 중 가장 작은 약수를 찾으면 되겠죠!