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

 

20. 다음은 1에서 100까지 소수의 개수를 구하는 프로그램이다. cnt = 0; for (i = 2; i <= 100; i++) {   prime = 1;   j = 2;   while ( ㉠ ) {     if (i % j == 0) prime = 0;     j++;   }   cnt += prime; } printf("%d\n", cnt);   다음 중 ㉠에 들어갔을 때 올바른 답이 출력되지 않는 것은? ① j <= i ② j < i ③ j < i - 1 ④ j <= i / 2 ⑤ j * j <= i

풀이) 소수란 1과 자기자신 만으로 나누어 지는 수

① j <= i  이 들어 가는 경우 어떤 값이 와도 cnt가 증가하지 않는다

   예)   I 값이 4 인경우 j가 4 까지 증가 되어 4%4 = 0 이 되므로 prime 값이 0 이 되며 cnt는 증가하지 않는다.

② j < i  => 2 부터 자기 자신보다 하나 작은 수까지 나누면서 나머지가 있는 경우에는 prime 가 남아 있어 소수에서 cnt 가 증가한다.

③ j < i - 1 => 2 부터 자기자신보다 두개 작은 수까지 나누면서 체크

    이때 i가 3인 경우 while 문을 들어가지 않지만 원래 3은 소수이므로 cnt가 증가 되는게 맞다

④ j <= i / 2  => 2부터 자기자신의 절반 값만을 비교 하는데 1/2 만 비교해도 됨

    I/2 의 값 동안 나누어 떨어지는 수가 없었다면 그 이후의 값으로 나누어서 떨어질 수 없다.

예) 31 을 15까지 비교해서 나누어 떨어진 수가 없다면 15보다 큰수로 나누어서 떨어지지는 않는다. 33과 같은 경우 3에서 나누어 떨어지므로 16까지만 비교해도 문제 없다.

⑤ j * j <= i   => 나누는 수의 제곱승의 값까지만 비교해도 됨(약수로 나누어 지지 않는다면 소수이다)

예) 100까지의 숫자를 비교 할때 2~10 까지의 숫자만으로 나누어 보면됨

만약 10 보다 큰 숫자중 자기자신을 제외한 수로 나누어 떨어지는 수라면 몫이 2 ~ 10까지의 숫자임

따라서 몫이 있고 나머지가 없다면 이미 2 ~ 10 사이로 나누어서 떨어진 경우이므로 굳이 계산할 필요가 없다.

정답) 1번