[문제] 백준 4948번 베트르랑 공준 - 소수

* 출처: 백준 단계별로 풀어보기 기본수학2

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

에스트라테네스의 체를 이용해 문제를 풀었다.

여기서 주의할 점은 반복문 돌릴 때 인덱스 범위이다.

i*i를 할 때 MAX_NUM을 넘어가면 안되고, 2*n할 떄도 마찬가지로 MAX_NUM을 넘어가면 안된다!

이부분만 주의하면 나머지는 앞선 소수 찾기 문제와 동일하다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static boolean[] prime;
	public static int MAX_NUM = 123456 * 2;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = 0;
		
		prime = new boolean[MAX_NUM + 1];
		initPrime();
		while ((n = Integer.parseInt(in.readLine())) != 0) {
			int ans = 0;
			
			for(int i=n+1;i<=2*n;i++) {
				if(i>MAX_NUM) break;
				
				if(!prime[i]) ans++;
			}
			sb.append(ans).append('\n');
		}
		System.out.println(sb);

	}

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

		for (int i = 2; i <= MAX_NUM; i++) {
			if (prime[i])
				continue;
			if(i*i>MAX_NUM) break;
			for (int j = i * i; j <= MAX_NUM; j += i) {
				prime[j] = true;
			}
		}
	}
}