CodeDrive

이 문제도 에라토스테네스의 체의 원리를 사용해서 풀어야 하는 문제이다. 하지만 입력이 하나의 테스트 케이스가 아니라 여러 개의 테스트 케이스로 이루어져 있으므로 매번 에라토스테네스의 체를 이용해 배열을 만드는 것은 시간을 많이 소비하게 된다. 따라서 미리 한 번 최대케이스에 대해서 경우로 만들어 놓고 테스트케이스들에 대해서는 슬라이싱을 통해서 접근을 하도록 한다.

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1<=M,N<=1,000,000)

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

임의의 수 n이 소수인지 판별하기 위해서 n-1까지 다 나눠보는 것이 아니라 sqrt(n) 값까지 나눠서 나누어지지 않는다면 소수임을 알 수 있다는 것은 대부분 알고 있다. 하지만 1,000,000개의 수에 대해서 다 해보는 것은 아무리 sqrt(n) 값까지 나눠본다고 해도 많은 시간이 소요된다. 따라서 이렇게 큰 수가 소수인지 판별하기 위해서 사용되는 것이 에라토스테네스의 체이다.

 이 방법은 예를 들어 120이하의 소수들을 파악하기 위해서 120까지의 배열을 생성한 뒤에 우선 2가 소수인지 판별을 한다. 2는 소수인것이 자명하므로 2의 배수의 값을 0으로 바꾼다.(4,6,8,10,12,14,......) 다 바꾸고 난 뒤에 3도 소수이므로(쉽게 판별할 수 있다.) 3의 배수의 값들을 0으로 바꾼다.(6,9,12,15,.....)이후 원래 4의 값으로 이동을 했지만 이미 2의 배수의 경우일 때 0으로 바뀌어 있다. 0이면 어떤 소수의 배수임을 의미하므로 그냥 지나가게 설정을 한다. 이렇게 계속 0이 아닌 수를 만나면 소수인지 판별을 하고 0을 만나면 그냥 지나가도록 한다. 그러면 최종적으론 이 배열엔 소수와 0만 남아있는 배열이 된다.

그러면 set을 통해서 중복된 0의 값들을 다 제거하고 재정렬한뒤 0의 값을 빼준다면 소수만 남아있는 리스트가 된다. 따라서 이 문제도 에라토스테네스의 체 방법을 이용해서 풀면 시간초과가 발생하지 않고 풀 수 있다.