JAVA백준 문제풀이 (11) 1929: 소수 구하기

 

 

백준 문제 밑에 항상 짧게 설명이 있다.

 

 

 

 

 

헉 더 빠르게 소수를 판별하는 문제?????? 정답률 26.666%??????

주어진 시간이 2초나 되길래 혹시나 싶어 그냥 풀어보니 다른 문제랑 똑같았다. 혹시 BufferdReader를 쓰지 않으면 시간 초과하나?

아니면 문제 번호가 1929번인 걸 보니 아직 코테가 당연하지 않던 시절에 사람들이 너무 틀려서 정답률을 낮춰놨나 싶기도 하다.

 

아무튼 그냥 에라토스테네스의 체로 풀 수 있는 문제였음.

모른다면 아래 링크에서 이전 포스트를 읽어봅시다.

 

제목은 백준 풀이인데 며칠째 소수 구하는 문제만 풀고 있어서 풀이를 적을 게 없다..

 

 

https://7357.tistory.com/104?category=1065986 

0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체

 

 

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int minNum = Integer.parseInt(st.nextToken());
        int maxNum = Integer.parseInt(st.nextToken());

        boolean[] isCompositeNum = new boolean[10000001];
        isCompositeNum[0] = isCompositeNum[1] = true;
        // 1과 0은 합성수도 소수도 아니다.. 임의 표현

        for ( int i = 0; i*i <= maxNum; i++ ) {
            if ( !isCompositeNum[i] ) {
                for ( int j=i*i; j <= maxNum; j+=i) {
                    isCompositeNum[j] = true;
                }
            }
        }

        for ( int i=minNum; i<=maxNum; i++) {
            if (!isCompositeNum[i]) {
                System.out.println(i);
            }
        }
    }
}