[백준] 1929번 : 소수 구하기 - JAVA [자바]

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

1929번: 소수 구하기

---

• 문제

 

 

 

이번 문제는 에라토스테네스의 체를 이용하여 풀어보는 정석적인 문제다!

알고리즘 분류에도 에라토스테네스의 체로 분류되어 있다.

 

---

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

문제를 들어가보면 알겠지만 알고리즘 분류에도 에라토스테네스의 체로 분류되어있는만큼 해당 알고리즘으로 풀어볼 것이다.

 

소수를 구하는 방법은 여러가지가 있지만 에라토스테네스의 체가 가장 대중적이면서 알고리즘 효율이 매우 좋은편인 방법이다.

소수를 구하는 방법에 대해 좀 더 자세히 알아보고자 하면 아래 포스팅을 참고하시라

 

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

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

 

 

입력은 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();
				
		for(int i = M; i <= N; i++) {
			// false = 소수 
			if(!prime[i]) System.out.println(i);
		}
	}


	// 에라토스테네스의 체 알고리즘
	public static void get_prime() {
		// true = 소수아님 , false = 소수 
		prime[0] = prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			if(prime[i]) continue;
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}
}

 

 

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

 

위의 알고리즘에 대한 자세한 설명은 앞서 참고하라던 포스팅에서 자세하게 다루니 원리를 이해하기 힘들다면 꼭 읽어보길 바란다.

---

- 방법 2 

 

그런데 출력 할 소수가 많아서 출력 호출 횟수가 많아질 수 있으니 조금이나마 성능을 개선하기 위해 하나의 문자열로 연결시킨다음 한 번에 출력시키도록 변경 할 수도 있다.

 

이 때는 StringBuilder 을 사용하면 되겠다.

 

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();
				
		StringBuilder sb = new StringBuilder();
		for(int i = M; i <= N; i++) {
			// false = 소수 
			if(!prime[i]) sb.append(i).append('\n');
		}
		System.out.println(sb);
	}


	// 에라토스테네스의 체 알고리즘
	public static void get_prime() {
		// true = 소수아님 , false = 소수 
		prime[0] = prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			if(prime[i]) continue;
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}
}

---

- 방법 3 

 

 

BufferedReader 을 사용하는 방법이다. 

알고리즘 자체는 앞선 방법들이랑 똑같고, 다만 입력방법만 달리 할 뿐이다.

 

이때 문자열 분리를 위해 StringTokenizer 을 쓸 것이다.

 

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


public class Main {
	public static boolean[] prime;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		prime = new boolean[N + 1];
		get_prime();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = M; i <= N; i++) {
			// false = 소수 
			if(!prime[i]) sb.append(i).append('\n');
		}
		System.out.println(sb);
	}

	public static void get_prime() {
		// true = 소수아님 , false = 소수 
		prime[0] = prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(prime.length); i++) {
			if(prime[i]) continue;
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}
}

 

---

- 방법 4

방법 3 에서 굳이 소수 배열 따로, 검사 따로 하는 방법이 아니라 소수인지 아닌지 판별과 동시에 소수라면 바로 그 변수를 출력하는 방법이 있다.

 

다만, 이 방법은 첫 반복문이 Math.sqrt(), 즉 최댓값의 제곱근까지만 순회하는 것이 아니라 최댓값까지 계속 순회해야 가능하다.

또한, 이중 반복문의 내부 반복문은 int j = i * i 을 할 경우 입력 최댓값이 1,000,000 이라 i 가 최대 1,000,000 가 된다면 j 의 경우 1,000,000,000,000 으로 int 형 범위를 넘어버릴 수 있어 int j = i + i 로 변경하여 풀어야 한다.

 

위 두가지 사항만 고려하면 아래와 같이 변경할 수 있다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        boolean[] prime = new boolean[N + 1];
        
        for(int i = 2; i <= N; i++) {
        	if(prime[i]) continue;
        	
        	if(i >= M) sb.append(i).append('\n');
        	
        	for(int j = i + i; j <= N; j += i) {
        		prime[j] = true;
        	}
        }
        
        System.out.println(sb);
    }

}

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 19298058  -  BufferedReader (방법 4)

채점 번호 : 19297971  -  BufferedReader (방법 3)

채점 번호 : 19297933  -  Scanner + StringBuilder (방법 2)

채점 번호 : 19297874  -  Scanner + System.out.println (방법 1)

 

 

보다시피 입력방법과 출력 방법에 따라서도 성능차이가 많이 난다.

---

• 정리

 

에라토스테네스의 체를 이용한 방법을 제대로 쓴 문제다.

 

이후 문제들 중에서도 소수를 구하는 문제들이 얼마나 있을지는 모르겠지만, 적어도 에라토스테네스의 체를 완벽히 이해하는 계기가 되었으면 한다.

 

고로 참고하라고 하는 포스팅을 꼭 읽어보았으면 좋겠다.