백준 - 1929

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

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        for (int i = start; i <= end; i++) {
            if (isPrime(i)) {
                sb.append(i).append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    public static boolean isPrime(int num){
        if(num < 2) return false;
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}

풀이과정 및 리뷰

• 소수를 구하는 최적의 방법은 i = 2부터 루트num까지의 숫자로 num을 나눠보는것

• boolean isPrime(int num) 메서드

  • 숫자가 2보다 작다면 무조건 false (소수는 2부터 시작하므로)
  • 루프는 i = 2 부터 num 까지돌면서 한번이라도 나머지가 0인 경우 false 반환하며 종료
  • 살아남는다면 true 반환

• 메인 for문

  • i = start 부터, i <= end 까지 루프를 돌며 isPrime 메서드가 true 인 경우 StringBuilder 에 해당 숫자를 넣어줌
    

• 에라토스테네스의 체
  - 2부터 시작해서 특정 수의 배수들을 지워나가면 남은 수들이 소수라는 원리

  ```

  [target = 30, i * i < 30으로 루프를 도므로 i는 5의 배수까지 확인]
  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

[2의 배수 제거]
2 x 4 x 6 x 8 x 10 x 12 x 14 x 16 x 18 x 20 x 22 x 24 x 26 x 28 x 30

[3의 배수 제거]
2 3 x 5 x 7 x 9 x 11 x 13 x 15 x 17 x 19 x 21 x 23 x 25 x 27 x 29

[5의 배수 제거]
2 3 5 7 11 13 17 19 23 29 (소수만 남음)