[백준] 1929 소수 구하기 자바

알고리즘/백준

[백준] 1929 소수 구하기 자바

보름달빵 2024. 11. 19. 22:01

문제

[백준] 1929번 소수구하기 문제

방법1- 일반적인 소수 구하는 방법으로 풀기

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 기본적인 방법으로 소수 판별하기
        sb = new StringBuilder();
        for(int i=M;i<=N;i++){
            checkPrimeNumber(i);
        }

        // 결과 출력
        bw.write(String.valueOf(sb));
        bw.flush();

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

    // 소수인지 판별하는 메서드
    public static void checkPrimeNumber(int num){
        if(num<=1) return;
        for(int i=2;i<= Math.sqrt(num);i++){
            if(num%i==0) return; // 소수가 아님
        }
        // 소수인 경우
        sb.append(num).append("\n");
    }


}

방법2- 에라토스테네스의 체 방법 적용하기

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] arr = new boolean[N+1];

        // 배열 초기화
        for(int i=2;i<=N;i++){
            arr[i]=true;
        }

        // 에라토스테네스의 체
        for(int i=2;i<=Math.sqrt(N);i++){
            if(!arr[i]) continue; // 이미 지워진 수는 건너뛰기
            for(int j=i+i;j<=N;j+=i){ // 배수 지우기
                if(!arr[j]) continue; 
                arr[j]=false;
            }
        }

        // 남은수 -> 소수 출력하기
        for(int i=M;i<=N;i++){
            if(arr[i]){
                bw.write(i+"\n");
            }
        }
        br.close();
        bw.flush();
        bw.close();

    }
}