[Java] 백준알고리즘 #4948 베르트랑 공준

백준알고리즘 #4948 베르트랑 공준 문제

 

n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 문제이다.

 

소수는 자기 자신과 1로만 나누어지는 수이므로 다음과 같이 구할 수 있겠다.

for (int i = n + 1; i <= 2 * n; i++) {
	for (int j = 1; j < i; j++) {
		if (i % j == 0) {
			primeCheck++;
		}
	}
	if (primeCheck == 1) {
		count++;
		primeCheck = 0;
	} else
		primeCheck = 0;
}

n보다 크고 2n보다 작은 범위를 지정 한 후 for문을 이용해 반복하면서 1부터 i까지의 수로 나누어 0이된다면 primeCheck를 1씩 증가시킨다. for문이 끝난 후 primeCheck가 1이라면 (1로만 나누어진다면) 이 수는 소수가 되므로 count를 1 증가 시킨후 primeCheck를 0으로 초기화해준다.

 

이러한 방법으로 쉽게 구할 수 있지만 이 방법의 단점은 시간이 아주 오래 걸린다는 것이다.

때문에 백준알고리즘 사이트에 제출해도 시간 초과라는 결과만 돌아오게 된다.

 

이를 해결하기 위해 에라토스테네스의 체를 사용한다.

2020/12/08 - [Java/백준알고리즘] - 백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)

백준알고리즘 #1929 소수 구하기 java (에라토스테네스의 체)

에라토스테네스의 체를 이용하여 소수를 구하는 방법은 앞선 포스팅에서 이미 확인해본 방법이므로 이를 응용하여 문제를 해결하면 되겠다.

import java.util.Scanner;

public class Back1929 {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int count = 0;
			int[] a = new int[2 * n + 1];
			for (int i = 1; i <= 2 * n; i++) {
				for (int j = 1; j <= n; j++) {
					if (i * j > 2 * n)
						break;
					a[i * j]++;
				}
			}
			for (int i = n + 1; i <= 2 * n; i++) {
				if (a[i] == 1)
					count++;
			}
			System.out.println(count);

		}
	}
}

문제의 조건에서 0을 입력하면 종료된다고 했으므로 0이 입력되기 전까지는 계속 반복되어야 한다.

따라서 while문을 이용하였고 조건인 0을 입력받았을때 빠져나가기 위해 if break 구문을 사용했다.

이후 에라토스테네스의 체를 이용하여 배열을 생성 한 후 n+1 ~ 2n 까지의 범위를 지정하여 그 사이의 소수의 개수를 카운트하여 출력해주면 된다.