JUNOTE

백준 17103번: 골드바흐 파티션 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 각 테스트 케이스 별로 짝수 N이 주어졌을 때, a + b = N 을 만족하는 두 소수 a, b 순서쌍의 개수를 구하는 문제이다. 단, 두 소수의 순서가 다른 순서쌍은 같은 파티션으로 취급한다. 문제를 풀기 위해서 에라토스테네스의 체를 이용해 소수를 판별해 주어야 한다. 에라토스테네스의 체에 대한 부분은 저번 포스팅을 참고해..

백준 1929번: 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 예제 문제해석 및 풀이 이 문제는 주어진 숫자 2개와 그 사이에 있는 모든 소수를 출력하는 문제이다. 크게 2가지 방법으로 이 문제를 해결할 수 있다. 첫 번째는 지난 4134번 문제에서 사용했던 찾는 숫자의 제곱근까지의 탐색을 통하여 소수를 찾는 방법, 두 번째는 에라토스테네스의 체를 이용하는 방법이다. 두 방법 중에서 전자는 후자에 비해 40배 정도의 시간이 더 걸렸다. 다만 메모리는 에라..