더블릿_rprime

서로 소라는 단어에 대해서 로직을 생각해내는 것이 핵심인 문제 같다. 

더 좋은 방법이 있을 수도 있지만(서로소의 성질을 이용해서 답을 도출해내는 등등)

나는 단순하고 무식하게 풀었다. 

두 숫자 input_a, input_b가 있다면

1) 두 숫자 중에 더 작은 수를 찾아냈다.

=> 작은 숫자의 약수를 구하는 이유는 작은 숫자가 큰 숫자보다 for문을 조금이라도 덜 돌수있기때문이다. 큰상관은 없다.

2) 1부터 작은 수까지 for문을 돌면서 작은 수의 약수를 모두 구해서 배열에 담아 두었다. 

3) 큰 숫자를 구해진 작은 수의 약수들로 나누어보아서 나누어지면 두 수는 서로소가 아니다.

어느 숫자로도 나누어지지 않으면 두 수는 서로소이다. 

물론 구해진 약수 중 1은 제외이다. 1은 어느 숫자라도 약수로 가지기 때문이다.

답이 제대로 나온다. 

이렇게 1000까지는 다소 후한 제약조건이 있는 경우에는 위와 같은 방법으로도 충분히 풀 수 있으므로 

크게 고민 할 필요가 없다. 

다만 숫자가 커지거나 하면 다른 방법을 생각해봐야 한다.