백준 BaekJoon 1644번: 소수의 연속합 [Java] 자바

2020-09-12

---

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다.

몇 가지 자연수의 예를 들어 보면 다음과 같다.

 

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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

소스코드

		int n = scan.nextInt();
		int count = 0;
		int [] arr = new int [n];
		arr[0] = 2;
		int k = 1;
		int sum = 0;
		
		for(int i = 3 ; i <= n ; i++) {
			loop :for(int j = 2 ; j < i ; j++) {
				if(i % j == 0) {
					count++;
					break loop;
					//j로 나누어 0이 되면, 
					//소수가 아님
				}
			}
			if(count == 0) {
				arr[k] = i;
				k++;
				//카운트가 0일 경우 해당 i의 값은 소수
				//배열에 집어넣음
			}
			count = 0;
			//다음 i값 비교를 위해
			//count 초기화
		}
		
		for(int i = 0; i < arr.length; i++ ) {
			if(arr[i] == 0) {
				break;
			}
			loop : for(int j = i; j < arr.length; j++ ) {
				if(n > sum) {
				sum += arr[j];
				//n이 더크면 계속 더해
				//근접한 수로 만들어줌
			}else if(n == sum) {
				count++;
				break loop;
				//n이 같아지면 그수는 소수의 연속합이 되고
				//카운트에 하나 더해줌
				}else {
					break loop;
					//sum이 더커지면 연속합이 아니기때문에
					//루프 탈출 다음 i값을 비교함
				}
			}
			sum = 0;
			//다음 값 더해주기 위해  sum을 초기화
		}

	   System.out.println(count);

 

출처 링크 : www.acmicpc.net/problem/1644

1644번: 소수의 연속합