[백준 / BOJ] 1644 소수의 연속합

1644번 : 소수의 연속합

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

문제를 풀면서 필요했던 것은

1. 에라토스테네스의 체

2. 투 포인터

의 개념이었다.

 

1. 에라토스테네스의 체

숫자를 더하고 빼가면서 그 때마다 소수인지를 가늠하는 것은 비효율적이기 때문에, 자연수 N의 최대값인 4,000,000까지의 배열을 만들고, 각 숫자가 소수인지 먼저 찾았다.

 

소수란, 1과 자신 외에 약수가 없는 수를 말한다.

 

1) 그럼 가장 먼저 떠오르는 것은 2부터 4,000,000까지 for문을 돌리면서 자신보다 큰 수 중 자신으로 나눠지는 수가 있는지 확인하는 것이다. 하지만 이 경우 3,999,998! 번의 연산이 필요하다. 너무 큰 수이기 때문에 차이를 확인하기 위해 10,000으로 나눴다. 2부터 400까지 숫자 중 소수를 고르기 위해 총 79,401번의 연산이 필요했다.

boolean[] not_prime = new boolean[401];

for(int i = 2; i <= 400; i++) {
	for(int j = i + 1; j <= 400; j++) {
    	if(j % i == 0) not_prime[j] = true;
    }
}

 

2) 그 다음으로 떠오르는 것은 2부터 2,000까지 일 것이다. 조건 내에 가장 큰 수인 4,000,000이 2,000의 제곱수이기 때문에, 어떤 N도 2,000보다 큰 수를 약수로 가질 수 없다. 하지만 이 역시 자신보다 큰 수 중 자신으로 나눠지는 수가 있는지 확인한다면 3,800,000! 번의 연산이 필요하다. 400으로 바꾼다면 총 7,391번이다. 아까보다 획기적으로 줄었지만 N을 400으로 제한해서 그럴 뿐, 4,000,000으로 가면 어림도 없다.

boolean[] not_prime = new boolean[401];

for(int i = 2; i <= 20; i++) {
	for(int j = i + 1; j <= 400; j++) {
    	if(j % i == 0) not_prime[j] = true;
    }
}

3) 반대로 생각하면 어떨까? 400을 기준으로, 2부터 20까지 수의 배수는 소수가 아니다. 나눠서 확인하는 것이 아니라 곱해서 확인하는 것이다. 단순히 반대로 바꿨을 뿐인데, 연산 수가 1,015번으로 줄었다. 배수가 아닌 수는 넘어갈 수 있기 때문이다.

boolean[] not_prime = new boolean[401];

for(int i = 2; i <= 20; i++) {
	int tmp = 2;
    while(tmp * i < 401) {
    	not_prime[tmp * i] = true;
        tmp++;
    }
}

4) 여기에 한 가지를 더 추가하자면, "어떤 수 i가 소수가 아니라고 밝혀졌다면, 그 i의 배수는 계산할 필요가 없다". 예를 들어 i가 6이라고 해보자. 6의 배수는 6, 12, 18, 24... 로 이어진다. 그리고 그 모든 수들은 6의 약수인 2 혹은 3으로도 당연히 나눠진다. 따라서 이미 어떤 수가 소수가 아니라고 밝혀졌다면, 그 수의 배수는 구할 필요가 없다.

이 조건까지 추가한 것이 에라토스테네스의 체이고, N의 최댓값이 400일 때 총 572번의 연산으로 소수를 가늠할 수 있다.

for (int i = 2; i <= 20; i++) {
	if(not_prime[i]) continue;
	int tmp = 2;
	while(tmp * i < 401) {
		not_prime[tmp * i] = true;
		tmp++;
	}
}

 

2. 투 포인터

소수를 구했다면 이제 N을 만들 수 있는 연속한 소수를 구해야 한다. 이미 어떤 수가 소수인지 알기 때문에 두 개의 포인터인 start와 end를 첫 번째 소수인 2에 두고, sum(연속합) 역시 2로 둔다.

 

start가 end보다 작은 동안 진행하며, end가 N이 될 수 있는 가장 큰 값인 4,000,000와 같거나 작을 때에만 동작하도록 조건을 주었다.

 

만일 sum이 주어진 N보다 작다면 더 큰 값을 더해줘야 하므로 end를 움직인다. 단, 이 때 +1로 끝내면 안되고, not_prime이 false인 값이 나올 때까지 계속 움직여준다. 이 과정에서도 제한값 4,000,000을 넘어갈 수 있기 때문에 계속 확인해줬다.

 

반대로 sum이 주어진 N보다 크다면 값을 빼줘야 하므로 start를 움직인다. 이 역시 단순히 +1이 아니라 소수가 나올 때까지 계속 돌려준다.

 

sum이 N과 같다면 카운트를 올리고, end를 움직여준다. 이 때는 사실 start, end 중 어느 것이든 움직여도 상관 없다.

int start = 2;
int end = 2;
int sum = 2;
int cnt = 0;
		
while(start <= end && end < 4000001) {
			
	if(sum < N) {
		end++;
		while(not_prime[end]) {
            		end++;
			if(end > 4000000) break;
		}
		sum += end;
	} else if(sum > N) {
		sum -= start;
		start++;
		while(not_prime[start]) {
        		start++;
             		if(start > end) break;
        	}
	} else {
		cnt++;
		end++;
		while(not_prime[end]) {
            		end++;
			if(end > 4000000) break;
		}
		sum += end;
	}
}

 

3. 결과물

백준에 제출한 답이라 변수명이 다른 것들이 있다. 

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		boolean[] num = new boolean[4000001];
		
		for (int i = 2; i <= 2000; i++) {
			if(num[i]) continue;
			int tmp = 2;
			while(tmp * i < 4000001) {
				num[tmp * i] = true;
				tmp++;
			}
		}
		
		int start = 2;
		int end = 2;
		int sum = 2;
		int cnt = 0;
		
		while(start <= end && end < 4000001) {
			
			if(sum < N) {
				end++;
				while(num[end]) {
                    end++;
					if(end > 4000000) break;
				}
				sum += end;
			} else if(sum > N) {
				sum -= start;
				start++;
				while(num[start]) {
                    start++;
                    if(start > end) break;
                }
			} else {
				cnt++;
				end++;
				while(num[end]) {
                    end++;
					if(end > 4000000) break;
				}
				sum += end;
			}
		}
		
		System.out.println(cnt);
	}

}