문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

  • 3 : 3 (한 가지)
  • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
  • 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net/problem/1644

  • 입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

  • 출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

과정

처음에는 에라토스테네스의 체를 제대로 구현하지 못해서 시간초과가 떴다. 소수를 그냥 구하느냐, 에라토스테네스의 체로 구하느냐에 따라 시간 차이가 많이 났다.

또 쓸데없이 투포인트 구현하는데 이중 while문을 썼다. 바보인가. 아래는 처음 구현한 코드이다.

def isPrime(n):
    i = 2
    while(i*i<=n):
        if n % i == 0:
            return False
        i += 1
    return True

n = int(input())
check = [True]*(n+1)
check[0] = check[1] = False
prime = []

for i in range(2,n+1):
    if isPrime(i):
        prime.append(i)

i = j = res = 0
while i <= len(prime):
    while j <= len(prime):
        if sum(prime[i:j+1]) == n:
            res += 1
            i += 1
            j += 1
        elif sum(prime[i:j+1]) > n:
            i += 1
        else:
            j += 1
    break

print(res)

최종 코드

아래는 에라토스테네스의 체를 제대로 구현한 코드이다.

n = int(input())
prime = []

check = [True]*(n+1)
check[0] = check[1] = False

# 에라토스테네스의 체
i = 2
while(i*i<=n):
    if check[i] == True:
        for j in range(i*2, n+1, i):
            check[j] = False
    i += 1

for i in range(1, n+1):
    if check[i]:
        prime.append(i)

# 투포인트로 연속합 찾기
i = j = res = 0
while j <= len(prime):
    if sum(prime[i:j+1]) == n:
        res += 1
        i += 1
        j += 1
    elif sum(prime[i:j+1]) > n:
        i += 1
    else:
        j += 1

print(res)

참고 사이트