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

 

 

문제풀이)

    c = 0;
    for (i = 1; i <= 30; i++)
    {
        d = 0;
        for (j = 1; j <= i; j++)
        {
         if ( (i % j) != 0) d++; <-- ⓐ
        }
        if (i == d + 3)  <-- ⓑ
            c++;
    }
    printf("%d\n", c);

========================

소스를 분석 하면 1부터 30까지 숫자중에서

1과 자기자신을 제외한 단 한개의 숫자로만 나누어지는 경우임

(  ⓐ 에서 d의 값은 나누어지지 않는 갯수 이며 ⓑ 에서 i 가 d + 3 인 경우 증가 되므로 1부터 자기자신까지의 숫자 중에서 1과 자기자신은 반드시 나누어 지므로 1과 자기자신을 제외한 단 한개의 숫자만으로 나누어 지는 경우에만 c의 값이 증가 됨)

따라서

i 값이 4 일때  1,2,4

         9 일때 1,3,9

         16 일때,1,2,4,8,16

         25 일때 1,5,25

이렇게 3가지 경우임

이 경우를 제외한 소수 인경우는 1 과 자기 자신처럼 나눌 수 있는 수는 단 2개이며

다른 수 들은 최소 4개 이상이 됨,

 

정답) 1번