2581. 소수 (자바, Java)

앞 문제와 별로 다를건 없는데, 커다란 문제가 생깁니다. 바로 시간제약.

앞서 언급한 Brute-Force로는 해결이 안됩니다. 시간초과가 되버리기 때문.

저같은 경우, 자바로는 풀리지만 백준에선 제출하니 시간초과로 떠서, 찾아보고 개념공부를 한 뒤 다시 짰습니다.

 

우선 필요한 시간복잡도 개념.

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

 

 기존의 방법 : N이하의 소수를 찾기 위해, N보다 작거나 같은 수 a를 2부터 a-1까지 각각 나눠본다. 나눠서 0이 나오는 수가 하나라도 있다면 소수.

 

 n까지를 n번 반복하므로, 시간복잡도는 O(n^2).

 

 먼저, 소수찾기 횟수 줄이기. n이 아니라 √n까지 반복합니다.

√n * √n = n이고, n의 곱 조합에서 √n보다 높은 수는 필연적으로 √n보다 낮은 수와 결합해야 합니다. 따라서, √n까지만 검사해도, √n 이상은 검사하지 않아도 됩니다.

 

ex) 16은 4*4 인데, 4보다 큰 8은 4보다 작은 2와 결합되고...하는 식입니다.

 

 두번째, 에라토스의 테네스의 체 이용.

'소수의 배수는 소수가 아니다' 를 이용해서, 소수로 판명난 숫자들은 거르는 방법입니다. 소수의 배수가 왜 소수가 아니냐, 하실분 없겠죠? 1과 자기자신 외의 수인 소수로 나눌 수 있으니, 소수가 아닙니다.

그렇게해서 2의 배수를 거르고, 3의 배수를 거르고, 4의 배수...는 4가 2의 배수이니, 4의 배수는 곧 2의 배수이기도 하기에 이미 걸러졌으니 PASS (애초에 4는 소수가아님), 5의 배수를 거르고...하면서 넘어가면, 시간복잡도를 줄일 수 있습니다. 단, 어떻게 그걸 할 수 있을까? 에 대한 고민은 여전히 남지요.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int m = Integer.parseInt(br.readLine());
		int n = Integer.parseInt(br.readLine());
		int sum = 0;
		boolean[] prime = new boolean[n+1]; // false면 소수, true면 소수아님

		for (int i=0; i<=Math.sqrt(n); i++) {

			if (i<2) {

				prime[i] = true;
				continue;

			}

			if (prime[i] == true) {

				continue;

			}


			for (int j=i*i; j<prime.length; j+=i) {

				prime[j] = true;

			}



		}

		for (int i=m; i<prime.length; i++) {

			if (prime[i] == false) {

				sum+= i;

			}
		}

		if (sum == 0) {

			System.out.println(-1);

		} else {		
			System.out.println(sum);

			for (int i=m; i<prime.length; i++) {

				if (prime[i] == false) {

					System.out.println(i);
					break;

				}

			}
		}
	}

}