[에라토스테네스의 체] Java로 구현하기

에라토스테네스의 체 - 소수를 쉽게 구하는 체(거름망)

그림으로 알아보자. 우선 숫자를 100까지 써본다. 그 후 각 숫자에 따라서 그 수의 배수인 수들은 모두 제거해나가기 시작한다. 2를 고르고, 2의 배수를 모두 지우고, 3을 고르고 3의 배수를 모두 지우고, 4는 2의 배수로 지워져있기 때문에 4의 배수는 다시 지우지 않아도 된다. 이렇게 지워지고 남은 수들은 모두 소수이다. 왜냐면 자기 자신과 1을 곱해야 나오는 수이기 때문이다. 

출처: 위키백과 

100이 소수인지 확인하기 위해서 일일이 100보다 작은 모든 수들로 확인할 필요는 없다. 이 방식대로 하면 시간복잡도가 O(n^2)이 되어버리고 소수인지 판별하려는 숫자가 너무 커지게 되면 코드 실행 시간이 매우 커지게 될것이다. 하지만, 소수인지 확인하려는 수의 제곱근까지만 확인하여 시간복잡도를 줄일수 있다.

왜 제곱근까지만 확인해보아도 될까?
어떤 수 N에 관하여 그의 제곱근 sqrt(N)보다 큰 소인수는 존재할 수 없기 때문이다. 다시 말해 N을 sqrt(N)으로 나눈 값은 sqrt(N)보다 작아야 하기 때문이다. 

N이 소수인지 판별할 때 N보다 작은 모든 수에 관하여 일일이 하는 방법
(아래 코드는 1부터 10000까지 소수를 찾는 것이다. check[]배열에 1이 들어가면 합성수이다. 0이 들어가면 소수이다. 0과 1은 예외이므로 따로 처리하도록 한다. 이렇게 되면 j가 i의 소인수인지 확인하여 i가 소수인지 판별하게 되는것이다. 

int[] check = new int[10001];
		check[0] = 1;
		check[1] = 1;

		for (int i = 2; i < 10001; i++) {
			for (int j = 2; j < 10001; j++) {
				if (i % j == 0 && i != j) {
					check[i] = 1;
				}
			}
		}

 

N이 소수인지 판별할 때 sqrt(N)보다 작은 모든 수에 관하여 일일이 하는 방법

int[] check = new int[1001];
		check[0] = 1;
		check[1] = 1;

		for (int i = 2; i< 10001; i++) {
			for (int j = 2; j*j<=i; j++) {
				if (i % j == 0 && i != j) {
					check[i] = 1;
				}
			}
		}

이렇게 j의 범위만 j*j<=i로 바꿔주게 되면 시간복잡도는 훨씬 줄게 된다.

 

이와 관련하여 백준 문제 1929번, 2582번, 1978번을 풀어보면서 체득하면 훨씬 더 잘 이해가 될 것이다.