조건에 맞는 기약분수의 갯수
프로젝트 오일러의 71~73번 문제는 비슷하게 생겼는데, 실제로는 서로 상당히 다른 문제들이다. 서로 비교해보면 많은 생각을 하게 하는 문제들이다. 71번 주어진 범위의 기약분수 중에서 \( \frac {3}{7} \)보다 작으면서 가장 큰 분수의 분자를 찾는 문제다. 주어진 범위가 무려 백만까지므로 무식하게 보면 백만(Mega)×백만=1Tera번 루프를 돌리면 답을 찾을 수 있다. 하지만, 조금만 생각해보면 각 분모별로 \( \frac {3}{7} \)에 가까운 기약분수 하나씩만 비교해보면 된다. 간단하게 만들어보면 아래와 같다. 최대공약수 코드는 앞 포스팅의 코드를 활용. #include #include #include size_t GCDfast(size_t x, size_t y) { if (!x |..