[백준-2581번/Java] 소수

* 소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

* 1, 2 예외 처리 (1은 소수 아님, 2는 소수임)

* M, N이 같은 경우

* '에라토스테네스의 체'로 풀었다. (변형하여 O(n)의 시간 복잡도를 이룰 수 있다.)

* 제곱근 범위 나누기 법으로도 풀 수 있음.

  ; 소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다.

import java.io.*;
import java.util.*;

public class Main {

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

		Scanner scan = new Scanner(System.in);

		int M = scan.nextInt();
		int N = scan.nextInt();
		long sum = 0;
		int min = 10001;

		int[] arr = new int[N + 1];
		for (int i = M; i <= N; i++) {
			// 1 예외처리
			if (i == 1) {
				arr[i] = -1;
			} else {
				arr[i] = i;
			}
		}
		for (int i = M; i <= N; i++) {
			// 2 예외처리
			if (i == 2 || arr[i] == -1)
				continue;
			for (int j = 2; j <= N; j++) {
				if (i != j && i % j == 0) {
					arr[i] = -1;
					// 에라토스테네스의 체 (나눠 떨어지는 수의 배수를 모두 제외 시킨다.)
					for (int k = 2 * i; k <= N; k += i) {
						if (arr[k] == -1)
							continue;
						arr[k] = -1;
					}
				}
			}

		}

		for (int i = M; i <= N; i++) {
			if (arr[i] != -1) {
				sum += arr[i];
				min = arr[i] < min ? arr[i] : min;
			}
		}

		if (sum > 0) {
			System.out.println(sum);
			System.out.println(min);
		} else {
			System.out.println(-1);
		}

		scan.close();
	}

}

 

* 시간초과

import java.io.*;
import java.util.*;

public class Main {

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

		Scanner scan = new Scanner(System.in);

		int M = scan.nextInt();
		int N = scan.nextInt();
		int sum = 0;
		int min = 10001;
		for (int i = M; i < N + 1; i++) {
			int j = 2;
			while (true) {
				if (i == j) {
					sum += i;
					min = i < min ? i : min;
					break;
				} else if (i % j == 0) {
					break;
				} else {
					j++;
				}
			}
		}

		if (sum > 0) {
			System.out.println(sum);
			System.out.println(min);
		} else {
			System.out.println(-1);
		}

		scan.close();
	}

}