1929번

문제

• N이상 M이하의 소수를 모두 출력하는 문제

문제 해결 순서

1. 기본적으로 에라스토테네스의 체 방식을 이용한다.
   (1차 삽질 반복문으로 대충 구하려하니 당연하게도 시간초과가 떴다.)
   (2차 삽질 13번째줄의 반복문에 int j = i; 식을 썼었는데 컴파일 에러가 떴다. 여러 예제를 넣어보고 알아낸게,
   j를 i로 초기화 해버리면 숫자가 커졌을 때 i*j <= m 식에서 int형의 크기를 벗어날 수가 있다는 것이다.)

import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int m = scan.nextInt();
    // m+1만큼의 boolean 자료형 배열을 선언
    boolean arr[] = new boolean[m+1];
    // 1은 소수가 아니니 true로 초기화
    arr[1] = true;
    // 반복문을 돌며 i의 배수를 true로 초기화한다. (에라스토테네스의 체)
    for(int i = 2; i <= m; i++){
      for(int j = 2; i*j <= m; j++){
        arr[i*j] = true;
      }
    }
    // m까지 반복문을 돌며 arr[i]번째가 false라면 소수라는 뜻
    for(int i = n; i <= m; i++){
      if(!arr[i]){
        System.out.print(i+"\n");
      }
    }
  }
}