백준 1644번 소수의 연속합

< 백준 1644번 소수의 연속합 - 마포 코딩박 >

사용한 알고리즘: 에라토스테네스의 체, 투포인터


 입력된 어떤 수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 11~18)
 에라토스테네스의 체로 4000000 이하의 소수를 구합니다.

(2) (코드 20~36)
 '연속된' 소수들의 합으로 입력된 N 을 나타낼 수 있는 경우의 수를 구합니다.
 '연속된' 수의 합이므로 투포인터를 이용해 과정(1)에서 구해놓은 소수들을 처음부터 끝까지 O(N) 의 시간복잡도로 탐색합니다.