[Java] 백준 - 4948번: 베르트랑 공준

4월 19일(수) - 약수, 배수와 소수2(4948번)

4948번: 베르트랑 공준

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static boolean[] prime = new boolean[123456*2 +1];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        get_prime();

        while (true)
        {
            int n = Integer.parseInt(br.readLine());
            if( n==0)
            {
                break;
            }

            int count=0;
            for(int i=n+1; i<=2*n; i++)
            {
                if(!prime[i])
                {
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    public static void get_prime(){
        prime[0] = prime[1] = true;

        for(int i=2; i<=Math.sqrt(prime.length); i++)
        {
            if(prime[i])
            {
                continue;
            }
            for(int j=i*i; j< prime.length; j+=i)
            {
                prime[j] = true;
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

풀이출처 -> https://st-lab.tistory.com/85