[구름 Level2]인싸가 되고 싶은 민수

https://level.goorm.io/exam/49089/%EC%9D%B8%EC%8B%B8%EA%B0%80-%EB%90%98%EA%B3%A0-%EC%8B%B6%EC%9D%80-%EB%AF%BC%EC%88%98/quiz/1

구름LEVEL

import sys, math
input = sys.stdin.readline()

def check(n):
	for i in range(2, int(math.sqrt(n))+1):
		if n % i == 0:
			return i			
	
	return n

a,b = map(int,input.split())
if a==b:
	print(check(a))
else:
	print(2)

* n/2 의 수까지 약수를 검사할 경우, 시간 복잡도에서 통과하지 못함.

-> math.sqrt를 통해 제곱근까지만 약수인지 검사하도록 수정.

 

처음에는 약수를 숫자 별로 계산하여 배열 약수 값 index에 1씩 더하여 배열의 최대 값 index를 찾아서 출력해줬는데,

큰수가 나올경우 out of memory 에러 발생.

 

그러던 중 숨어있는 규칙 발견.

a=b 이면, 약수 중 가장 작은 수 출력(1 제외)
a!=b 이면, 2 출력