백준_4948 - JAVA

---

- 알고리즘

. 구해야 하는 범위의 최대값은 123456 ~ 246913 이다.(2 * n)

. 1부터 246913 까지의 모든 수에 대해서 소수인지 아닌지를 기록한 boolean 배열을 이용하여 구한다.

 

. 제곱수는 어짜피 소수가 아니기 때문에 2부터 2*n의 제곱근 까지 반복을 돌아 주며 소수 배열을 구한다.

. 현재 i의 제곱 부터 i씩 증가 되는 수는 소수가 아니기 때문에 true 를 넣어 주는 식으로 소수를 배열을 구할 수 있다.

	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;
			}
		}
	}

 

. 이렇게 소수 배열을 구하고 나면 main 에서 n ~ 2*n 사이의 수를 모두 배열과 대조 해 보면서 소수인 수를 count 해 주는 식으로 쉽게 구할 수 있다.

---

- 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class B_4948 {

	public static boolean[] PRIME = new boolean[246913];

	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;
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		Get_Prime();

		while(true){
			int N = Integer.parseInt(br.readLine());
			if(N == 0){
				break;
			} else if(N == 1){
				bw.write("1" + "\n");
			} else {
				int Cnt = 0;
				for (int i=N+1; i<2*N; i++){
					if(!PRIME[i]){
						Cnt += 1;
					}
				}
				bw.write(Cnt + "\n");
			}
		}


		bw.flush();
		bw.close();
	}
}