에라토스테네스의체

[백준] 6588 - 골드바흐의 추측 (자바/Java)

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

[백준] 1929 - 소수 구하기 (자바/Java): 에라토스테네스의 체

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 앞의 문제들처럼 풀었다가 시간 초과가 났다. 에라토스테네스의 체를 사용하는 문제였다. 에라토스테네스의 체는 소수를 구하는 알고리즘으로, 2부터 자기 자신을 제외한 자신의 배수들을 하나씩 지워나가는 알고리즘이다. 이때 끝까지 남아있는 수들이 소수에 해당한다. 그래서 먼저 배열을 선언하여 각 값을 초기화하였다. 이때 index를 그 값으로 사용하기 위해 N+1 크기의 배열을 선언하였다. 그리고 배열을 돌며 값이 0인 경우..