소수의 연속합

어제 진행했던 코딩테스트에서 소수의 연속합 문제가 나와서 글로 남겨보려한다.

문제

(나의 기억에 의존이니 정확하지 않을 수 있다.)

자연수 N, M이 주어진다. 자연수 N이하의 소수들을 조합하여 합이 M이 되게 하려한다. 단 소수들은 연속되어야 한다. 이때 가능한 조합의 가지수를 반환해야한다.

예를 들어 N= 20, M= 36인 경우를 생각해보자.

36이하의 소수들은 2, 3, 5, 7, 11, 13, 17, 19가 있다. 이 중 연속된 소수를 선택하여 합이 36인 경우를 찾아야한다.

문제 조건을 만족하는 경우는 5 + 7 + 11 + 13 = 36 과 17 + 19 = 36 두 가지 뿐이다.

따라서 2를 반환해야한다.

문제 풀이과정

1. N이하의 소수를 에라토스테네스의 체 방법으로 구한다.
2. start, end 두개의 포인터를 이용한다.
3. 현재 부분합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분합이 M이상 이라면 end 증가를 중지한다.
5. 현재 부분합이 M이라면 answer(반환값)을 1 증가시킨다.
6. 현재 부분합을 맨 앞의 값(소수[start])만큼 감소시키고 start를 1 증가시킨다.

코드

import math

def solution(N,M):
  answer = 0
  prime_number = []
  array = [True for _ in range(N + 1)]

  for i in range(2, int(math.sqrt(N)) + 1):
      if array[i]:
          j = 2
          while i * j <= N:
              array[i * j] = False # i의 배수들을 차례로 제거한다.
              j += 1

  for num in range(2, N + 1):
      if array[num]: # 남겨진 수들만 prime_number에 담는다
          prime_number.append(num)

  interval_sum = 0
  end = 0

  for start in range(len(prime_number)):
      while interval_sum < M and end < len(prime_number): # 문제 풀이과정 2,3 
          interval_sum += prime_number[end]
          end += 1

      if interval_sum == n: # 문제 풀이과정 5
          count += 1
      interval_sum -= prime_number[start] # 문제 풀이과정 6

   return answer

출처

https://bbbyung2.tistory.com/82