백준 4948번 자바 베르트랑 공준 [기본수학2] 에라토스테네스의 체

문제가 개떡같이 길게 쓰여 있지만 간단하게 풀면

n을 입력하면 n보다 크고 2n보다 작은 소수의 개수를 출력하는 문제이다.

0을 입력할 때 까지 계속 반복하면 끝~

 

저번 소수문제와 같이 이렇게 범위가 주어지고 소수를 구하는 문제는 에라토스테네스의 체 방법을 이용하면 된다.

 

마찬가지로 같은 방법을 이용해서 풀어보도록 하자.

hellodoor.tistory.com/114

백준 2581번 자바 소수 [기본 수학2] 에라토스테네스의 체

에라토스테네 체의 관한 자세한 풀이는 요기에 있다.

import java.util.Scanner;
 
public class Main {
    //baekjoon 4948 베르트랑 공준 기본수학2
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true) {
            int n = sc.nextInt();
            if(n==0) {
                break;
            }
            boolean arr[] = new boolean[2*n+1];
            arr[0] = true;
            arr[1] = true;
            
            for(int i=2; i<=Math.sqrt(2*n+1); i++) {
                for(int j=i*i; j<2*n+1; j+=i) {
                    arr[j] = true;
                }
            }
            int cnt = 0;
            for(int i=n+1; i<2*n+1; i++) {
                if(arr[i] == false) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}