[ Baekjoon - 10/19 ] - 1644번: 소수의 연속합

• 문제 링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 1024MB
   • 문제
     
     • 자연수 N(1≤N≤4,000,000)
     • N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제
   • 이해
     • 문제이해도 어렵지 않고, 소수라는 말만 봐도 에라토스테네스의 체를 이용하는게 최선이므로, 바로 구현방법이 떠올랐다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제이해가 어렵지 않아서 생략하겠다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 에라토스테네스의 체와 투포인터 배열)

   • 

   • 소수를 에라토스테네스의 체를 이용해 구한뒤, 해당 소수를 누적한 값을 arr배열에 저장한다.
   • sp(시작 포인터), ep(끝 포인터) 두 값을 설정해 sp~ep까지의 합이 목표한 N보다 크다면 sp+=1, 작다면 ep+=1, 같다면 카운트 증가 하는 방식으로 구할 수 있다.
4. 위 계획을 검증
   • 소수는 해당 알고리즘을 통해 잘 구할 수 있고, sp와 ep를 같은 출발지점으로 두어서 여러값이 나올 수 있다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.lang.reflect.Array;
        import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,ans=0,sp=0,ep=1;
            static boolean[] isPrime;
            static List<Integer> arr;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                N = Integer.parseInt(br.readLine());
        
                isPrime = new boolean[N+1];
                isPrime[0] = true;
                isPrime[1] = true;
        
                arr = new ArrayList<>();
                arr.add(0);
                
                for (int n = 2; n <= N; n++) {
                    if (!isPrime[n]) {
                        // arr에 소수 누적합 추가
                        arr.add(arr.get(arr.size() - 1) + n);
                        // 에라토스테네스의 체 구현부
                        for (int i = 2; i * n <= N; i++) {
                            isPrime[i * n] = true;
                        }
                    }
                }
        
                int lenArr = arr.size();
                while (sp <= ep && 0<=sp && sp<lenArr && ep<lenArr) {
                    // curSum = sp+1 ~ ep 까지의 합
                    int curSum = arr.get(ep) - arr.get(sp);
                    if (curSum < N) {
                        ep += 1;
                    } else if (curSum > N) {
                        sp += 1;
                    } else {
                        ans += 1;
                        sp += 1;
                    }
                }
                System.out.println(ans);
            }
        }

         
   2. Python 3

      1. import sys
         
         input = sys.stdin.readline()
         
         N = int(input)
         
         isPrime = [False for _ in range(N+1)]
         isPrime[0] = True
         isPrime[1] = True
         
         arr = [0]
         for n in range(2,N+1):
             if not isPrime[n]:
                 arr.append(arr[len(arr)-1]+n)
                 for i in range(2,N):
                     if i*n<=N:
                         isPrime[i*n]=True
                     else:
                         break
         
         
         lenArr = len(arr)
         ans=0
         sp=0
         ep=1
         while sp<=ep and 0<=sp<lenArr and  ep<lenArr:
             curSum = arr[ep] - arr[sp]
             if curSum<N:
                 ep+=1
             elif curSum>N:
                 sp+=1
             else:
                 ans+=1
                 sp+=1
         print(ans)

 

• 결과