[java 백준] 실버 2/1929번 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] arr = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            arr[i] = i;
        }
        for (int i = 2; i <= N; i++) {
            if (arr[i] == 0) {
                continue;
            }
            for (int j = i + i; j <= N; j += i) {
 
                arr[j] = 0;
            }
 
        }
        for (int i = M; i <= N; i++) {
            if (arr[i] != 0) {
                System.out.println(arr[i]);
            }
        }
 
    }
 
}

예를 들어 i가 2면 j는 4부터 시작한다. arr[4],arr[6] .. 모두 합성수이기 때문에 0으로 바뀐다.

i가 3이면 j인 6,9,12... 는 0으로 바뀐다. 

i가 4이면(이미 4는 합성수여서 0이 됐고) j는 8,12,16.. 인데 어차피 얘네는 다 0으로 이미 바뀌어있다.

 

이렇게 2i부터 시작해도 합성수이면 이미 앞에서 다 0으로 바뀌기 때문에 걱정할 필요 없다.