허비의 기술블로그

숫자 N이 주어지면, N보다 작거나 같은 소수들의 연속합으로 N을 만들 수 있는 개수를 출력하는 문제이다. 더하는 소수는 연속된 숫자이다. (3 + 11 = 14는 안된다.) 시간 복잡도: O(N) 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 과정 소수의 연속합이 N이 되는 지를 구하려면 N보다 작거나 같은 소수들의 리스트를 구해야 한다. N까지의 소수를 찾는 과정은 에라토스테네스의 체를 활용하면 O(N)의 시간으로 구할 수 있다. N보다 작거나 같은 소수들의 리스트를 구하면, 이후에는 투포인터 알고리즘을 활용해서 첫 원소에서 마지막 원소까지 각 연속합이 N과 같은 개수를 카운트해주면 된다. 투포인터 알고리즘도 두 개의..