[소수 찾기] 에라토스테네스의 체

에라토스테네스의 체 (Sieve of Eratosthenes)

고대 그리스 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법

마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 불림

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법

수학 공식 : f(x)=1P​(x)x​

 

원리

시작 전 간단하게 이해하기 위해 아래 2분 30초짜리 영상으로 확인해보자

[출처:비상교육] https://www.youtube.com/watch?v=G1_6A9Ifi3o

1. 1~100까지의 수가 있음

2. 1은 소수가 아니므로 걸러냄

3. 소수 2는 남기고, 2의 배수(짝수)는 모두 걸러냄

4. 소수 3을 남기고 3의 배수를 모두 걸러냄 

=> 계속 반복 후 남은 숫자들이 소수임

 

에라토스테네스의 체 사용 전

처음에 아무것도 모르는 상태에서 코드를 작성했을 때는 이론적으로만 맞게 작성하였다.

public class Main {
	public static int cnt = 0;
	public static int num = 100;
	public static void main(String[] args) {
		for(int i=1;i<num;i++) {
			if(!is_prime(i)) continue;
			System.out.println(i);
			cnt++;
		}
		System.out.println("Total : "+ cnt);
	}
    
	public static boolean is_prime(int x) {
		for(int i=2;i<x;i++) {
			if(x%i==0) return false;
		}
		return true;
	}
}

하지만 코드를 넣어 실행하면 매번 시간초과가 발생해서 인터넷에 검색해보니

x에 들어오는 값이 소수일 경우 x를 2부터 x-1까지 나눠보기 때문에

내가 작성한 코드의 시간 복잡도가 O(N)이 나오게 된다

 

시간복잡도 낮추기

시간복잡도를 낮추기 위해 x로 들어오는 값을 나눠보는 범위를 바꾸어야 한다

기본적으로 숫자는 약수의 곱으로 이루어져 있다

그리고 해당 숫자를 나눌 때 나누는 값과 몫 둘 중에 하나는 무조건 해당 숫자의 제곱근보다 같거나 작다 

예를 들어 10인 경우 2*5이면서 동시에 5*2인데, 나누는 값이 2이면 몫이 5이고 나누는 값이 5이면 나머지가 2이다

2로 나누어 봤으면, 굳이 세트인 5로 나누어보지 않아도 되는 것이다

따라서 판별하려는 숫자가 n일때 2부터 n-1까지 나누어 보는 것이 아니라 2부터 n의 제곱근까지만 확인하면 된다

import java.lang.Math;

public class Main {
	public static int cnt = 0;
	public static int num = 100;
	public static void main(String[] args) {	
		for(int i=1;i<num;i++) {
			if(!is_prime(i)) continue;
			System.out.println(i);
			cnt++;
		}
		System.out.println("Total : "+ cnt);
	}
	public static boolean is_prime(int x) {
		for(int i=2;i<=Math.sqrt(x);i++) {
			if(x%i==0) return false;
		}
		return true;
	}
}

이 방법을 사용했을 때 n의 제곱근까지만 확인하므로 시간 복잡도는 O($N^{\frac{1}{2}}$)가 된다

이런 방법으로 시간복잡도는 낮췄지만 이건 단순히 하나의 숫자가 소수인지 판별할때만 효율적이다

대량으로 들어오는 숫자들을 일일이 소수인지 판별하기 위해서는 더 효율적인 방법이 필요하다

그래서 공부하게 된 것이 에라토스테네스의 체다

 

에라토스테네스의 체 사용

본격적으로 에라토스테네스의 체를 사용하기 위해 숫자 n의 크기보다 1이 큰 배열을 만들어준다 (인덱스 0부터 시작하기 때문)

1. boolean 타입의 배열 prime을 생성한 후, 인덱스 0과 1은 false로, 나머지는 true로 초기화

2. 2부터 시작해서 값이 true일 경우 해당 배수를 모두 지운다

     (j에 해당 숫자 i의 2배의 값을 넣은 후 j에 i를 계속 더해나가면서 해당 인덱스 값을 false로 바꾼다)

3. 배열의 인덱스 2부터 n까지 값이 true인 인덱스를 모두 출력한다

import java.lang.Math;

public class Main {
	public static int cnt = 0;
	public static int num = 100;
	public static boolean[] prime = new boolean[num+1];
	public static void main(String[] args) {
		primeNumber();
		System.out.println("Total : "+ cnt);
	}
	public static void primeNumber() {
		prime[0]=prime[1]=false;
		
		for(int i=2;i<=num;i++) {
			prime[i] = true;
		}
		
		for(int i=2;i<=num;i++) {
			if(!prime[i]) continue;
			for(int j = i*2;j<=num;j+=i) {
				prime[j]=false;
			}
		}
		
		for(int i=2;i<=num;i++) {
			if(prime[i]) {
				System.out.println(i);
				cnt++;
			}
		}
	}
}

참조 : https://blog.naver.com/ndb796/221233595886

문제 추천 [백준 4948] : https://www.acmicpc.net/problem/4948