[백준알고리즘-JAVA]1929번 풀이(소수구하기) - 초보도 이해하는 풀이

안녕하세요

인포돈입니다.

백준 알고리즘 1929번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1929 (소수 구하기)

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오..

입력

입 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

입력 예시

3 16

출력 예시

3
5
7
11
13

실패 코드 (시간 초과)

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));
	   	 
	   	 	String[] str = br.readLine().split(" ");
	   		int min = Integer.parseInt(str[0]);
	   		int max = Integer.parseInt(str[1]);
	   		StringBuilder sb = new StringBuilder();

	   		int s = 0;
	   		
	   		for(int i = min ; i <= max ; i++) {
	   			if(i !=1) {
	   				for(int j = 2 ; j <= (int)Math.sqrt(i) ; j ++) {
	   				if(i%j == 0) {
	   					s += 1;
	   				}
	   				}
	   				if(s == 0 ) {
	   					sb.append(i).append("\n");
	   					
	   				}
	   				s = 0 ;
	   			}
	   		}
	   		System.out.println(sb.toString());
		}
		}

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class test {
	public static void main(String args[]) throws IOException{
	   	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	String[] str = br.readLine().split(" ");
	   		int min = Integer.parseInt(str[0]);
	   		int max = Integer.parseInt(str[1]);
	   		StringBuilder sb = new StringBuilder();
	   		
	   		boolean[] nbox=new boolean[max+1];
	   		nbox[0] = nbox[1] = true;
	   		

	   		for(int i = 2 ; i <= Math.sqrt(nbox.length) ; i++) {
	   			if(nbox[i]) continue;	//이미 소수로 판별되었으면 아래 FOR문을 생략
	   			for(int j = i*i ; j < nbox.length ; j +=i)	//배수값을 TRUE로 바꾸어 소수에서 제외
	   				nbox[j] =true;
	   		}
	   		
	   		
	   		for(int i = min ; i <= max ; i++)
	   			if(!nbox[i]) sb.append(i).append("\n");
	   		
	   		System.out.println(sb.toString());
		}
}

 

해당 알고리즘은 이전에 참고했던 소수, 소수 찾기에 이어서 소수 구하기이다. 해당 알고리즘은 이전 글을 참고한다면 쉽게 해결할 수 있다.

[백준알고리즘-JAVA]2581번 풀이(소수) - 초보도 이해하는 풀이

 

[백준알고리즘-JAVA]1978번 풀이(소수 찾기) - 초보도 이해하는 풀이

그러나 그런 식으로 알고리즘을 코딩한다면, 시간 초과가 나올 것입니다.

 

해당 알고리즘에서 가장 중요한 것은 바로 에스 토스 테네스의 체 기법을 사용하여 소수를 구해야 하기 때문입니다.

 

이번 알고리즘 풀이는 에스 토스 테네스의 체에 집중적으로 알아보겠습니다. 이외의 소수 찾기는 위에 올려놓은 링크를 참고 바랍니다 ~!!

---

알고리즘 흐름도

입력받기 -> 에스 토스 테네스의 체로 소수 구하기 -> 반복문으로 구한 소수들 출력

---

STEP1 에스토스테네스의 체

 

알고리즘을 이해하기 전에 에스 토스 테네스의 체에 대해서 정말로 간략하게 알려드리겠습니다.

 

에스 토스 테네스의 체에 대해서 검색하시면, 정말 훌륭한 정보들이 많습니다. 이를 종합해서 한마디로 정의하자면,

 

저희가 소수인지 판별하려는 숫자가 N이라면

 

2 ~ ROOT(N)까지 정수를 반복하면서 그 배수를 지워준다입니다.

 

만약 N이 16이라면

2, 3, 4를 반복하는 거죠

1 ~ 16의 숫자 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2의 배수 : 2 4 6 8 10 12 14 16

3의 배수 : 3 6 9 12 15

4의 배수 : 4 8 12 16

 

여기서 2의 배수 3의 배수 4의 배수의 중복된 수를 제거하고 작성해보면

 2 3 4 6 8 9 10 12 14 15 16 이 됩니다.

 

여기서 기본적으로 1은 소수에서 제외가 되고 각배수의 첫 번째 수도 배수가 아니게 되죠.

 

따라서 4 6 8 9 10 12 14 15 16은 제외가 됩니다.(단 그 수보다 낮은 수의 배수가 된다면 지워야 합니다 EX) 4 ) 그렇게 해서 남은 수는

 

2 3 5 7 11 13 이 소수로 판별이 되는 겁니다.

 

이런 식으로 진행되는 게 바로 에스 토스 테네스의 체입니다.

 

---

STEP2 고려해야 하는 점

 

1. boolean 배열을 선언해서 true, false로 소수를 판별해야 한다.

(반듯이는 아닙니다.)

다른 배열을 이용할 시 각자의 방법으로 소수를 판별할 수 있도록 하시면 됩니다. 단 boolean배열을 이용하여 풀이하시는 게 시간이 가장 단축된다는 점!!

 

2. 배열을 선언할 때는 max크기보다 1을 더해야 한다.

0은 소수 찾기에서 제외됨으로 그 크기를 더해주어야 합니다.

 

3. 앞서 1을 제외하기 위해서 미리 true로 값을 초기화시켜놓고 시작하셔야 합니다.

index 0 은 0을 제외하기 위해서 true로 초기화

index 1 은 1이 소수가 아니기 때문에 true로 초기화

 

4. if(nbox [i]) continue;

해당 코드는 앞서 살펴본 4와 같은 경우를 제외하기 위해서 사용됩니다.

continue를 사용하면 다시 상위 for문 i++로 가게 됩니다. 즉, 아래에 있는 소수 찾기인 j for문을 돌지 않게 되죠

 

---

해당 STEP을 다 고려하시면 알고리즘은 쉽게 코딩될 수 있습니다!