[백준/JAVA] 1929번 소수 구하기

내 풀이 1 : 시간초과

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        // M 이상 N 이하의 모든 소수 출력하기

        // for문을 돌려서 안나눠지면 출력한다.
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int M = sc.nextInt();
        int N = sc.nextInt();

        // M 이상 N 이하의 수를 출력하는 for문
        for (int i = M; i <= N; i++) {//3~16
            // 소수인지 판별하기 위한 flag값을 준다.
            boolean flag = true;

            // 소수인지 아닌지를 판별하는 for문
            // 한 번이라도 나뉘어 지면 소수가 아니므로 false값을 준다.
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0){
                    flag = false;
                }
            }
            // 한 번도 나뉘어지지 않고 i가 1보다 크면 추가한다.
            if (flag == true && i > 1){
                sb.append(i);
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());
    }
}

내 풀이 2 : 인프런 - 에라토스테네스 체 문제 풀이 참고 - 정답

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {

        // M 이상 N 이하의 모든 소수 출력하기

        // for문을 2부터 N까지 돌린다.
        // arr[i] == 0 일때 답에 추가한다.
        // 다시 for문을 i부터 N까지 j+i해서 돌린다
        // 답을 추가한 i의 배수들을 모조리 제거한다.
        // 다시 arr[i] == 0 일때 답을 출력한다.
        // 단, i가 M보다 클 때 출력한다.
        
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int M = sc.nextInt();
        int N = sc.nextInt();

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

        for (int i = 2; i <= N; i++) {
            if (arr[i] == 0) {
                if (i >= M) {
                    sb.append(i);
                    sb.append("\n");
                }

                for (int j = i; j <= N; j = j + i) {
                    arr[j] = 1;
                }
            }
        }
        System.out.println(sb.toString());
    }
}

느낀점

처음에 내 느낌대로 풀었더니 시간초과가 나왔다.
문제 참고에 에라토스테네스체가 있길래 전에 인프런 강의를 들으면서 풀었던 풀이를 찾아 참고하면서 풀었더니 정답을 맞혔다. 이 공식을 꼭 기억해야겠다.