[백준] 2581번 : 소수 - JAVA [자바]

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

2581번: 소수

---

• 문제

 

매우 간단한 문제다!

 

소수를 구하는 알고리즘은 에라토스테네스의 체를 사용할 것이다.

소수를 구하는 빠른 알고리즘을 알고싶다면 아래 글을 먼저 읽고오면 좋을 것 같다.

 

https://st-lab.tistory.com/81

소수를 구하는 알고리즘 - JAVA [자바]

---

• 2가지 방법을 이용하여 풀이한다.

 

기본적인 알고리즘은 에라토스테네스의 체를 사용한다.

다만 입력에 따라 Scanner 와 BufferedReader 을 통한 방법 두 가지를 보여주고자 한다.

 

 

---

• 풀이

- 방법 1 

 

 

import java.util.Scanner;
 
public class Main {
 
	public static boolean prime[];
	
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int M = in.nextInt();
		int N = in.nextInt();
		
		prime = new boolean[N + 1];	// 배열 생성 
		get_prime();
		
		
		// 소수 합 및 최솟값 
		int sum = 0;
		int min = Integer.MAX_VALUE;
		for(int i = M; i <= N; i++) {
			if(prime[i] == false) {	// false = 소수 
				sum += i;
				if(min == Integer.MAX_VALUE) {	// 첫 소수가 최솟값임  
					min = i;
				}
			}
		}
		
		if(sum == 0) {	// 소수가 없다면 
			System.out.println(-1);
		}
		else {
			System.out.println(sum);
			System.out.println(min);
		}
		
	}
 
	
	// 에라토스테네스 체 알고리즘 
	public static void get_prime() {
		prime[0] = true;
		prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
		
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

에라토스테네스의체 자체가 시간복잡도가 O(N㏒(㏒N)) 이라 매우 좋은 성능을 갖는다.

그래서 어지간한 문제에서는 위 방법을 앞으로도 자주 사용하게 될 것이다.

---

 

- 방법 2 

 

 

BufferedReader 을 쓰는 방법이다.

 

기본 알고리즘 자체는 완전 같은지라 입력부분만 신경써서 바꿔주면 된다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static boolean prime[];
	
	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());
		
		prime = new boolean[N + 1];	// 배열 생성 
		get_prime();
		
		
		// 소수 합 및 최솟값 
		int sum = 0;
		int min = Integer.MAX_VALUE;
		for(int i = M; i <= N; i++) {
			if(prime[i] == false) {	// false = 소수 
				sum += i;
				if(min == Integer.MAX_VALUE) {	// 첫 소수가 최솟값임  
					min = i;
				}
			}
		}
		
		if(sum == 0) {	// 소수가 없다면 
			System.out.println(-1);
		}
		else {
			System.out.println(sum);
			System.out.println(min);
		}
		
	}
 
	
	// 에라토스테네스 체 알고리즘 
	public static void get_prime() {
		prime[0] = true;
		prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			if(prime[i]) continue;	// 이미 체크된 배열일 경우 skip
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
		
	}
}

 

 

이 전 문제에서도 만약 필자의 포스팅을 봤었다면 알겠지만 알고리즘 자체가 거의 비슷비슷하다.

 

대부분 비슷한 접근법으로 매우 좋은 성능을 쉽게 적용할 수 있어 대개 소수문제는 위와 같은 방법으로 많이 접근하게 된다.

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 19296946  -  BufferedReader

채점 번호 : 19296871  -  Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

이번 문제는 그리 어렵지 않았을 것이라 본다.

 

필자가 앞서 읽어보라고 한 포스팅을 읽어본다면 백준에 있는 대부분의 소수문제들을 풀 수 있을 것이다.

그러니 읽어보는 것을 적극 권장한다.