https://www.acmicpc.net/problem/1644
시간 2초, 메모리 128MB
input :
- N (1 ≤ N ≤ 4,000,000)
output :
- 소수의 합으로 나타낼 수 있는 경우의 수를 출력
생각보다 오래 걸렸다...
동일한 투포인터 문제이다.
에라토스테네스의 체로 400만개의 숫자를 다 확인해도 되지만....
n + 1개 까지만 체크를 하자.. 효율적으로
그리고 입력을 받을 때 1보다 크거나 같은 자연수를 입력 받는데 이에 대한 예외처리를 해 주지 않아서 인덱스에러가 계속 발생했다.
그냥 temp 가 n 이 1보다 클 때만 더해 주도록 하자.
import sys
n = int(sys.stdin.readline())
nums = []
prime_num = [1] * (n + 1)
prime_num[0] = 0
prime_num[1] = 0
for i in range(2, n + 1):
for j in range(i + i, n + 1, i):
prime_num[j] = 0
for idx, item in enumerate(prime_num):
if item:
nums.append(idx)
start, end, ans = 0, 0, 0
if n > 1:
temp = nums[start]
while start < len(nums):
if temp >= n:
if temp == n:
ans += 1
temp -= nums[start]
start += 1
else:
if end == len(nums):
break
end += 1
if end != len(nums):
temp += nums[end]
print(ans)
