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

문제

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

check

1. 어렵게 보인다, 복잡해 보인다 라는 생각이 들면 어짜피 못풀거다 라는 생각에 생각하기를 멈춘다. 따지고 보면 그렇게 어려운게 아닌데 지레짐작해서 포기해버린다. 

 

2. 예전 코드를 보니 '소수는 귀찮다'라는 생각에 풀다 안 푼 흔적이 있다. 

3. 막상 해보면 별거 아니다. 

 

소스코드

package november.first;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class EratosDemo {
    public static boolean[] isPrime ;
    public static void main(String[] args) throws  Exception{
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =  new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int minNum = Integer.parseInt(st.nextToken());
        int maxNum = Integer.parseInt(st.nextToken());

        isPrime = new boolean[maxNum+1];
        Arrays.fill(isPrime, true);
        isPrime[0] =false;
        isPrime[1] = false;
        eratos(maxNum);

        for(int num = minNum ; num <= maxNum ; num++){
            if(isPrime[num]) bw.write(String.valueOf(num)+"\n");
        }
        bw.flush();

        br.close();
        bw.close();


    }
    public static void eratos(int maxNum){
        for(int num =2 ; num <= maxNum; num++){
            if(isPrime[num]){
                //num * n = x 에서 n 기준
                for(int n = 2; num*n<=maxNum ; n++){
                    if(isPrime[num*n]) isPrime[num*n] = false;
                }
            }
        }
    }

    public static void eratos2(int maxNum){
        for(int num = 2; num <= maxNum; num++){
            if(isPrime[num]){

                //num * n = x 에서 x기준
                for(int x = num*num ; x<=maxNum; x+=num){
                    isPrime[x] =false;
                }
            }
        }
    }
}