백준 4948 베르트랑 공준(Java)

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

4948번: 베르트랑 공준

---

 

해석 및 팁

 

---

 

이 문제는 에라토스테네스의 체를 활용하면 풀 수 있는 문제입니다. 2부터 2n까지의 수를 에라토스테네스의 체를 이용해서 걸러낸 후 n초과 2n이하의 소수를 list에 저장한 후에 list의 size를 출력해 주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;
import java.util.ArrayList;

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

    while(true) {
      ArrayList<Integer> list = new ArrayList<>();
      int n = sc.nextInt();
      if(n == 0) break;
      boolean[] arr = new boolean[2 * n + 1];
      for(int i = 2; i <= Math.sqrt(2 * n); i++) {
        if(arr[i] == true) continue;
        for(int j = i * i; j <= 2 * n; j+=i) arr[j] = true;
      }

      for(int i = n + 1; i <= 2 * n; i++) if(arr[i] == false) list.add(i);
      System.out.println(list.size());
    }
    
  }
}