백준 4948 베르트랑 공준 자바

이전 문제 소수 구하기의 코드에서 조금만 수정해서 풀었다!

https://hauoli.tistory.com/21

불러오는 중입니다...

 

(n의 최대값*2) 크기의 배열을 만들어서 소수인지 아닌지를 boolean형으로 표기하고

n이 들어오면 n~n*2 사이의 배열들을 보고 소수이면 count해주는 것으로 풀었다!

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

		int max = 1234567 * 2;
		boolean[] isPrimeNum = new boolean[max + 1];// false일때 소수

		isPrimeNum[1] = true;// 숫자 1은 소수가 아님

		for (int i = 2; i <= max; i++) {
			for (int j = 2; j * i <= max; j++) {// 특정 숫자의 배수들은 소수가 아님
				isPrimeNum[i * j] = true;
			}
		}

		while (true) {
			int n = sc.nextInt();
			if (n == 0) {// 입력 0이면 끝
				break;
			}
			int count = 0;

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