연속합과 투 포인터를 이용한 문제이다.
소수를 구하는 방법에는 여러가지가 있지만 시간복잡도 상에서 효율적인 에라토스테네스의 체를 이용하여 구한다.
이 문제에서 유의할 점은 입력이 된 숫자 본인도 쓰일 수 있다는 점이다.
나는 에라토스테네스의 체를 사용할 때 소수를 마킹하는 방법을 모든 리스트를 돌면서 나머지가 0인 지점을 마킹했는데 이러면 입력된 숫자가 매우 커지면 각 소수마다 n의 시간이 돌기 때문에 TLE가 뜨게 된다.
따라서 이를 for i in range(i+i, n, i)
즉 i가 소수라면 2i부터 n까지 i의 배수를 마킹하는 것으로 하여 시간복잡도를 줄였다.
나의 풀이
import sys
import math
num = int(sys.stdin.readline())
def primeset(num):
pr = [0 for i in range(num+1)]
tar = int(math.sqrt(num))
for i in range(2, tar+1):
if pr[i] == 0:
for j in range(i+i, num+1, i):
pr[j] = 1
return [i for i in range(2,num+1) if pr[i] == 0]
li = primeset(num)
# print(li)
prefix = [0]
presum = 0
for i in li:
presum += i
prefix.append(presum)
# print(prefix)
left = 0
right = 1
tar = num
ans = 0
num = len(prefix)-1
# print(prefix)
while left < right and right <= num:
if -prefix[left] + prefix[right] < tar:
right += 1
elif -prefix[left] + prefix[right] > tar:
left += 1
else:
# print(prefix[left], prefix[right])
ans += 1
left += 1
print(ans)