정보올림피아드 초등 - 지역예선] 2011년도 6번문제

문제풀이)

96을 소인수 분해하면 다음과 같다.

96 -- 2

48 -- 2

24 -- 2

12 -- 2

6 -- 2

3 

따라서 서로소가 되려면 2의 배수가 아니고 3의 배수가 아니어야 한다.

서로소를 추출해 보면

1,5,7,11,13,17,19,23,25,29,//31,35,37,41,43,47,49,53,55,59,//61,65,67,71,73,77,79,83,85,89,//91,95

과 같다.

모두 구하는 것 보다 다음과 같이 계산 하여 구할 수 있다.

96 개 중 2의 배수인 48 을 빼면 48 이 남는다.

96 개 중 3의 배수인 32를 빼면 16 이 남는다.

6의 배수를 두번 뺐기 때문에 96개중 6의 배수인 16을 더하면 32 가 된다.

따라서 정답은 32개 이다.