[백준] 4948번: 베르트랑 공준(소수, 에라토스테네스의 체)

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

4948번: 베르트랑 공준

코드

import java.util.Scanner;

public class Main {
	
	// n ~ 2n까지 수 중 소수의 갯수 리턴
	public static int isPrime(int n) {
		int count = 0;
		int j = 0;
		
		for(int i=n+1; i<=2*n; i++) {
			boolean check = true;
			for(j=2; j<=Math.sqrt(i); j++) {
				if(i%j == 0)	{
					check = false;
					break;
				}
			}
			
			// i%j == 0이 안됐을 경우 => 소수
			if(check) 	count ++;
				
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true) {
			int n = scan.nextInt();
			if(n == 0)
				break;
			System.out.println(isPrime(n));
			
		}
		
		scan.close();
	}

}

풀이

일반 소수찾기 문제와 동일하지만, 주어진 문제대로 그대로 구현할 경우 시간초과가 발생한다.

왜 ? 문제에서 주어진 n의 범위는 123,456이하인데,

n < x <= 2*n 의 범위이므로,

소수를 찾기 위해 2중 for문에서 200,000 * 200,000 정도만 해도 숫자가 커지기 때문에 시간초과가 발생한다.

따라서, 기존에 소수인지 판별하기 위해 j를 2 ~ i-1까지 나누는게 아닌 j를 2 ~ i의 제곱근까지 나누며 판단한다.

그럴경우 시간초과가 발생하지 않고 통과된다.

 

 

이 문제의 경우 구현, 에라토스테네스의 체 이므로, 에라토스테네스의 체로도 풀어보았다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다

그림의 경우,  11^2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다. 

즉, 제곱근 까지만 반복해도 충분하다는 것이다.

(출처: 위키백과)

 

 

위 과정을 요약하면, 소수는 1과 자기자신만이 약수를 가지는 수이므로, 2부터 시작해서 해당 배수를 지워가는 과정이다.

2의 배수 => 2, 4, 6, 8, 10, 12, ... -> 소수 X

3의 배수 => 3, 6, 9, 12, 15, 18, ... -> 소수 X

4의 배수 => 4, 8, 12, 16, 20, ... -> 소수 X

 

 

위 과정을 코드로 작성하면 아래와 같습니다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		while(true) {
			int n = scan.nextInt();
			if(n == 0) break;
			int count = 0;
			int nn = n*2;
			boolean[] data = new boolean[nn+1];
			data[0] = data[1] = false;	// 0, 1은 소수가 아니므로 false로 지정

			// data[]의 초기값 => true로 지정
			for(int i=2; i<=nn; i++)
				data[i] = true;

			// i, j의 배수 => 소수 아니므로 false로 체크
			for(int i=2; i<=Math.sqrt(nn); i++) {
				if(!data[i])	continue;	// 이미 걸러진 수의 배수는 pass
				for(int j=2; j*i<=nn; j++)
					data[i*j] = false;
			}

			for(int i=n+1; i<=nn; i++) 
				if(data[i])	count ++;

			System.out.println(count);
		}
		scan.close();
	}

}