[백준/2581/Java]소수

[백준/2581/Java]소수

풀이

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());
		boolean[] bool = new boolean[N + 1];
		int sum = 0;
		int min = -1;
		
		// 소수 구하기(에라토스테네스의 체)
		bool[0] = true;
		bool[1] = true;
		// N의 제곱근만큼 반복
		for (int i = 2; i < Math.sqrt(bool.length); i++) {
			for (int j = i*i; j < bool.length; j+= i) {
				bool[j] = true;
			}
		}
		
		// 주어진 범위의 소수 값 확인
		for (int i = M; i <= N; i++) {
			if(bool[i] == false) {
				sum += i;
				if(min == -1) min = i;
			}
		}

		if(sum != 0) System.out.println(sum);
		System.out.println(min);
	}
}

후기

저번 알고리즘에 이어서 소수를 구하는 예제입니다.

이번에는 해당 범위의 값이 소수인지 아닌지를 구하는 알고리즘이기 때문에 다른 방식으로 풀이를 하였습니다.

에라토스테네스의 체 알고리즘을 사용해서 풀이를 진행하였는데요

처음 1번 최대값만큼의 소수를 구하고 해당 범위의 값중에 소수를 찾는 방식입니다.

이러면 소수를 찾는 처리는 처음 1회만 돌기때문에 효율성 측면에서 좋았던 것 같습니다.