[백준 - 1644] 소수의 연속합

체로 소수를 만든 뒤, 연속한 소수 합이 목표값이 되는 구간을 찾은 풀이.

2022년 7월 18일

먼저 에라토스테네스의 체로 목표값 이하의 소수를 표시했다. 그다음 시작 소수를 하나씩 정하고, 다음 소수를 더해 가며 합이 목표값 이상이 될 때까지 확인했다.

start를 고정한다
다음 소수를 더한다
합이 N이면 경우의 수를 늘린다
합이 N을 넘으면 다음 start로 이동한다

소수 목록을 만들기 전에는 연속합을 검사할 수 없고, 목록을 만든 뒤에는 일반 수가 섞이지 않게 다음 소수로만 이동할 수 있다. 이 풀이에서는 소수 전처리와 연속 구간 탐색을 분리했다.