[JAVA] 백준 1644번 : 소수의 연속합

 

---

 

• 코드

정답 코드 : 소수의 값들을 boolean배열에 false로 해놓고(에라토스테네스의 체) 해당 인덱스를 ArrayList에 넣어둔다. HashSet이 아닌 ArrayList에 넣는 이유는 넣는 순서를 유지시키기 위함. 그리고 입력 값의 수를 세는 것은 주석으로 설명해 놨다.

에라토스테네스의 체, 투 포인터 방식 사용

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long N = Long.parseLong(br.readLine());
        ArrayList<Integer> primeNumber = new ArrayList<>();
		
        boolean[] prime = new boolean[(int) (N+1)];
        prime[0] = prime[1] = true;
        
        for(int i=2; i*i<=N; i++){
            if(!prime[i]) {
            	for(int j=i*i; j<=N; j+=i) 
            		prime[j]=true;      
            }
        }            
        for(int i=2; i<=N;i++){
        	if(!prime[i]) primeNumber.add(i);     
        }
        
        int start=0, end=0, sum=0, count=0;
        while(true) {
        	if(sum==N) {		
        		count++;
        		sum-=primeNumber.get(start++);
        	}
        	else if(sum>N) {	//sum이 N보다 커지면 작은 소수의 값부터 점점 빼줌
        		sum-=primeNumber.get(start++);
        	}
        	else if(end == primeNumber.size()) { //sum이 N보다 작은데 end의 위치가 primeNumber.size랑 같으면 더이상 더해줄게 없기때문에 break;
        		break;
        	}
        	else {		//sum이 N보다 작으면 소수의 작은 값부터 큰값으로 점점 더해줌
        		sum+=primeNumber.get(end++);
        	}
        }
        
        System.out.println(count);
    }
}