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

 

 

문제풀이) 우선 각각의 조건이 소수를 구하는 조건을 만족하는지 체크한다.

1) d <= n 인 경우 n 이 2 가 들어 오는 경우 f 의 값은 0 이 찍히므로 연산 오류

2) d < n 인 경우는 연산이 되지만 n - 1 번의 횟수를 연산 한 후에 print 됨

3) d < n - 1 인 경우는 2 와 3 인 경우는 소수 이므로 while 문 안의 프로세스를 수행 하지 않아도 되므로 연산이 됨, n-2 번의 횟수를 연산 한 후에 print 됨

4) d * d <= n 인 경우 제곱근으로 체크 하는 형식으로 최소의 횟수로 체크가 가능함

(예를 들면 n 이 100 까지의 임의의 수가 들어 온 경우 10 이전의 수로 나누어 지지 않는다면 소수이다. 10보다 큰 수로 나누어 진다는 말은 이미 10보다 작은 수로 나누어졌다는 이야기 임, 100 이하의 임의의 수가 13으로 나누어 진다면 그 이전에 10보다 작은 수로 나누어 졌다는 이야기임 13 * 1,13 * 2,13 * 3 ... 13 * 9 = 107 이므로 100보다 큰 수가 됨)

5) d * d < n 인 경우 n 이 4가 입력 된 경우 f = 1을 출력 하게 되므로 연산 오류임

정답) 4번