효준이는 학교에서 배수와 약수에 대해 배웠다.

어떤 자연수 A가 있고, 자연수 B로 A를 나누었을 때 나머지가 발생하지 않으면 A는 B의 배수,

B는 A의 약수라 한다. A, B가 같을 수도 있다.

효준이는 그래서 수를 아래와 같이 3가지로 분류해 보기로 했다.

(A) 1은 가장 작은 수이기 때문에 첫 번째 분류에 넣는다. (B) 2 이상의 자연수 중에서 1과 자기 자신을 제외한 '약수'가 하나라도 있으면 두 번째 분류에 넣는다. (C) 첫 번째와 두 번째 분류에 속하지 않는 모든 수가 세 번째 분류에 들어간다.

예를 들어, 1 이상과 10 이하의 자연수는 다음과 같이 분류된다.

분류1 : [ 1 ] 분류2 : [ 4 6 8 9 10 ] 분류3 : [ 2 3 5 7 ]

주어진 자연수 N에 대하여 1이상 N이하의 자연수들을 분류하였을 때

각 분류에 몇 개의 수가 포함되는지 출력하는 프로그램을 작성하시오.

숫자 분류 timer 1s memory 64MB

숫자 분류 1s 64MB