1. i와 n이 서로소가 아니라면 i가 n으로 나누어떨어지거나, 2 이상 루트i 이하의 공약수를 가집니다. sqrt(i)까지만 탐색하면 더 빨라질거예요
2. 함수를 사용할 수 있으시군요! 최대공약수가 아니라 그냥 공약수가 있는지만 알면 되니까 gcd 끝까지 구할 거 없이 그냥 2 이상의 gcd를 발견하면 반복문 내에서 바로 return i 하면 더 빠르게 찾을 수 있습니다.
3. 10주차에 배열을 배우고 나면 에라토스테네스의 체를 이용해서 보다 빠르게 풀 수 있을거예요
4. 굳이 최대공약수 찾을 것도 없는 문제지만 지금 제출하신 최대공약수 구하는 방법을 좀 더 효율적으로 바꿀 방안을 제안드리자면
초등학교 때 최대공약수를 구했던 방법을 떠올려보세요
8과 12의 최대공약수를 구할 때
2│8 12
─┼──
2│4 6
─┼──
│2 3
최대공약수는 2*2 = 4
이렇게 구했을 거예요
이처럼 a와 b를 줄여가면서 구하면 시간을 단축할 수 있습니다.
* 사실 제일 빠른 방법은 a와 b의 최대공약수는 a와 b%a의 최대공약수와 같다는 것을 이용하는 것입니다.
(a와 b의 최대공약수를 gcd라고 할 때, b%a도 gcd로 나누어떨어진다.
a와 b%a의 공약수 중 gcd보다 큰 공약수 gcd2가 있다면 a와 b도 gcd2로 나누어떨어지는데 gcd가 a와 b의 최대공약수이므로 gcd2가 있을 리 없다. 그러므로 gcd가 a와 b%a의 최대공약수다.)
