[ 백준 - 1929] [Java] 소수 구하기

 

 

이 포스팅은 자바 8버전으로 포스팅 됐습니다.

 

 

문제

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

입력

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

출력

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[]args) throws IOException {
        try {
            BufferedReader s_rd = new BufferedReader(new InputStreamReader (System.in));
            String text[] = s_rd.readLine().split(" ");
            // M = 시작 N = 끝
            int M = Integer.parseInt(text[0]);
            int N = Integer.parseInt(text[1]);
            boolean is_Prime[] = new boolean[N+1];
            
            for(int i=2;i<=N;i++){
                if(is_Prime[i])
                    continue;
                // boolean은 초기화시 기본 false을 갖는다.
                    
                for(int j=2;i*j<=N;j++) {
                    is_Prime[i*j]=true;
                }
            }
            is_Prime[0] = is_Prime[1] =true;
            for(int i=M;i<=N;i++){
                if(is_Prime[i]==false)
                    System.out.println(i);
            }
        }
        catch(IOException e) {
        }
    }
}

풀이

1번~7번은 문제에 필요한 클래스를 호출한다.

8~9번 라인은 입력을 위해서 작성됐다.

11~12번 사이 값을 구하기 위해서 시작 값을 M으로 끝 값을 N으로 정의한다.

boolean 타입을 활용하여 끝 값보다 1 여유 공간을 더 입력받도록 초기화한다. -> (1 ≤ M ≤ N ≤ 1,000,000) 조건이 있으므로 N보다 커야한다. 선언부를 끝냈다면 준비는 끝났다.

소수 찾기에 대한 로직을 생각해 보자.

소수 찾기 방법은 다음과 같다.

1. 찾고자 하는 범위의 자연수를 나열한다.

2. 1은 지운다.

3. 2부터 시작하여, 2의 배수를 지워나간다.

4. 다음 소수의 배수를 모두 지운다.

Java언어 특성상 배열[i]로 선언이 아닌 값을 모두 초기화한 경우 배열안에 모든 값은 false를 갖게 된다.

이후 '에라토스테네스 체' 풀이 방법을 활용하여 문제를 해결했다.

이후 is_Prime 배열 중 true를 제외한 값을 모두 출력한다.

 

---

 

잡담)

처음에 문제 풀이를 했을 때 시간 초과가 정말 많이 나왔습니다. 소수를 판별하는 문제는 이전에도 풀었는데 소수를 모두 갖고 오는 문제라 해답 방향을 잘못 잡아서 시간도 생각보다 많이 걸렸고, 그동안 풀었던 풀이 방법들이 최적화가 거의 안된 수준으로 해결을 위한 코드였다는 것을 느껴서 다음에 기회가 된다면 더 좋은 방법으로 풀이를 진행해야겠다 생각이 들었습니다.

코드가 맞지만 다른 사람들 제출 코드를 보면 10배 가까이 시간 차이가 났습니다.

아무래도 10배 가까이 시간 차이가 나는 이유는 잦은 for문을 활용하여 문제를 해결한 것이 시간을 많이 잡아먹은 것 같습니다. 다음에 문법과 문제 해결 능력이 더 좋아지면 코드를 손보면서 더 좋은 코드를 짤 수 있도록 노력해야겠습니다.

문제점이나 의문이 있는 경우 댓글 부탁드리겠습니다.

다음 포스팅 때 뵙겠습니다. 감사합니다.

 

참조

 

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전