백준 4948, 베르트랑 공준

문제

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

4948번: 베르트랑 공준

 

문제요약

1. 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있습니다.

2. 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

문제풀이

소수를 판별하기 위한 대표적인 방법은 어떤 수 N이 주어질때 2~N의 양의 제곱근까지 N이 나누어 떨어질때 합성수로 판별하고, 아닌 경우 소수로 판별합니다.

어떤 수 N이 주어질때 시작변수는 N+1이 되고 끝 변수는 2*N으로 저장하고 시작변수와 끝 변수 범위에서 소수를 구하면 됩니다.

 

소스코드

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


public class Main {
	
	public static boolean isPrime(int n)
	{
		for(int i=2; i<=(int)Math.sqrt(n); i++)
		{
			if(n%i==0)
			{
				return false;
			}
		}
		return true;
	}
	public static int solution(int n)
	{
		int start = n+1;
		int end = n*2;
		int cnt=0;
		for(int i=start; i<=end; i++)
		{
			if(isPrime(i) && i>1)
			{
				cnt++;
			}
		}
		return cnt;
	}
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true)
		{
			int n = Integer.parseInt(br.readLine());
			if(n==0)
			{
				break;
			}
			System.out.println(solution(n));
		}
		
	}
}