https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 2 + 2 , 8 -> 3 + 5 와 같이 소수 두개의 합으로 나타내는 표현이라고 한다. 10의 골드바흐 파티션은 (3 + 7), (5 + 5)이 있다. (3 + 7)과 (7 + 3)은 같은 파티션으로 간주한다고 하니, 10의 골드바흐 파티션은 2개가 나오는 것을 확인할 수 있다. 그러니 입력 받은 짝수 N을 소수로 뺀 값이 소수가 나오는 경우의 수를 세주면 ..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 해석 이 문제는 에라토스테네스의 체를 이용해서 소수들이 검사되어 있는 배열을 생성해주는 메소드를 만들어주고, 함수의 인자로 배열의 크기(2N), 검사할 수의 시작 인덱스(M)를 인자로 받아 반복문을 통해 해당 범위내의 소수의 수를 세준 뒤 return해주면 되겠다. 에라토스테네스의 체를 이해하기 위해서는 아래 링크를 참고해주시면 감사하겠습니다. [백준 / BOJ] 1929번 소수 구하..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 해석 이번 문제는 입력받은 M과 N 사이의 모든 소수들을 출력해주면 되는 아주 단순한 문제이다. 소수를 구하면 되니 에라토스테네스의 체를 이용하면 매우 효율적으로 구할 수 있다. 에라토스테네스의 체에 관해서는 이전 [소수 찾기] 문제에서 다룬적이 있다. 그런데 바로 지난 문제인 [다음 소수]를 풀며 깨달은 점은 내가 소수 찾기 문제에서 사용했던 에라토스테네스의 체는 반쪽짜리도 안되는 알고리즘이었다는 것이다. 그 이유는 에라..