백준 1664번 - 소수의 연속합

출처 : 1644번: 소수의 연속합 (acmicpc.net)

1644번: 소수의 연속합

---

소수의 연속합 성공출처다국어분류

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

14806

6369

4505

42.532%

문제

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

• 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과 같은 표현도 적합하지 않다.

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

입력

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

출력

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

 

---

[ 문제 설명 ]

 

( 해결 아이디어 )

 

소수인지 아닌지 판단하는 함수를 만들자 -> 에라 토스네의 체 이용

 

나머지는 2003번과 유사한 방법으로 풉니다.

 

2003번 참고용 주소  :  백준 2003번 - 수들의 합 2 (tistory.com)

백준 2003번 - 수들의 합 2

 

2003번과의 차이점은 배열 안에 들어가는 수들이 에라 토스네 체를 이용해서 return 한 수들이라는 점.

 

그 이후는 원리가 비슷합니다.

 

주석을 달아놓았으니 참고하시면서 이해하시기를 바랍니다.

 

---

[ 코드 ]

 

def prime_list(n):
    # 에라토스테네스의 채 초기화 n 개의 요소에 True 설정 (소수로 간주)
    sieve = [True] * n
    # n의 최대 약수가 sqrt(n) 이하 이므로 i = sqrt(n) 까지 검사

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i + i, n, i):  # i 이후, i 의 배수를 False 판정
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]  # 소수 목록


n = int(input())
target = n
primes = []
primes = prime_list(n + 1)
# print(primes)

left = 0
right = 0
sum = 0
res = 0

# 순서가 있어야 하는 이유가 있다. while 문이 종료되는 시점을 고려하면 이해 가능
while True:
    # 크기가 큰 경우
    if sum >= n:
        sum -= primes[left]
        left += 1

    # print(right, left)
    # 다 돈 경우
    elif len(primes) == right:
        break

    # 크기가 부족한 경우
    else:
        sum += primes[right]
        right += 1
    # 조건에 맞는 경우
    if sum == n:
        res += 1

print(res)

 

---

후기

 

연속적으로 비슷한 문제들로 풀었네요

 

헷갈렸던 개념이라면 확실하게 알게 되기도 했고

 

복습으로써 나쁘지 않은 포스팅 같네요