백준 1929 소수 구하기(Java)

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

1929번: 소수 구하기

---

 

해석 및 팁

 

---

 

이 문제는 에라토스테네스의 체를 활용하지 않으면 시간초과가 발생하므로 에라토스테네스의 체를 사용하여 풀어야 합니다.  먼저 0과 1은 소수가 아니므로 -1을 입력시켜 놓고 2부터 제곱근 n 까지 i의 배수를 찾으면 -1을 넣습니다. 최종적으로 m부터 n까지의 범위중 -1인 배열을 제외하고 StringBuilder에 저장시켜서 출력하면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int m = sc.nextInt();
    int n = sc.nextInt();
    int[] arr = new int[n+1];
    arr[0] = -1;
    arr[1] = -1;

    for(int i = 2; i <= Math.sqrt(n); i++) {
      if(arr[i] == -1) continue;
      for(int j = i + i; j <= n ; j += i) arr[j] = -1;
    }

    for(int i = m; i <= n; i++) {
      if(arr[i] != -1) sb.append(i +"\n");
    }

    System.out.println(sb);
  }
}