소수(prime number)와 에라토스테네스의 체

📌 연관 문제

1929번 소수 구하기

1978번 소수 찾기

6588번 골든바흐의 추측

 

📝 소수(prime number)란?

약수가 1과 자기 자신 밖에 없는, 1보다 큰 자연수.

한편 1보다 큰 자연수 중에서 소수가 아닌 것은 합성수(composite number)라고 한다.

소수의 개수는 무한하며, 이는 유클리드의 정리에 의해 증명되었다.

 

 

소수인지 아닌지 판단하기

N이 소수가 되려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

public class Main
{
	public static void main(String[] args) {
		int n = 3;
		if (isPrime(n)) {
		    System.out.println("소수군요!");
		} else {
		    System.out.println("합성수군요!");
		}
	}
	
	private static boolean isPrime(int n) {
	    if (n < 2) {
	        return false;
	    }
	    
	    for (int i = 2; i <= n - 1; i++) {
	        if (n % i == 0) {
	            return false;
	        }
	    }
	    
	    return true;
	}
}

 

하지만 이 코드의 시간복잡도는 O(n)으로 조금 더 최적화해 보도록 하자!

 

N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

어떤 수 N이 소수가 아니라면, N = a * b로 나타낼 수 있다.

가능한 a 중에서 가장 작은 값은 (1과 자기 자신을 제외하고) 2이기 때문에, b는 N/2를 넘지 않는다.

즉, N/2과 N사이에는 약수가 없다는 것을 알 수 있다.

N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문에 다음과 같이 코드를 작성할 수 있다.

public class Main
{
	public static void main(String[] args) {
		int n = 3;
		if (isPrime(n)) {
		    System.out.println("소수군요!");
		} else {
		    System.out.println("합성수군요!");
		}
	}
	
	private static boolean isPrime(int n) {
	    if (n < 2) {
	        return false;
	    }
	    
	    for (int i = 2; i <= n/2; i++) {
	        if (n % i == 0) {
	            return false;
	        }
	    }
	    
	    return true;
	}
}

 

하지만 여전히 시간복잡도는 O(n)이다.

O(n/2)에서 1/2은 상수이며, 이는 시간복잡도 계산에서 무시되기 때문이다.

 

N이 소수가 되려면, 2보다 크거나 같고 √n보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

어떤 수 N이 소수가 아니라면,  N = a * b로 나타낼 수 있다.

그럼 a와 b 중 적어도 하나는 √n 이하이다.

N = a * b (단, N은 소수가 아니다)
만약, 두 수가 모두 √n보다 크다면 두 수의 곱은 n보다 크다.
a ＞ √n, b ＞ √n 이면 a * b ＞n
따라서 a와 b 중 적어도 하나는 √n 이하임을 알 수 있다.
a ≤ √n 또는 b ≤ √n

 

a가 b보다 작거나 같다고 했을 때, a가 될 수 있는 건 2 ~ √n이므로

그 a에 해당하는 b는 √n보다 큰 약수가 된다.

N = a * b (단, N은 소수가 아니다)(a ≤ b) 일 때,
a = 2 ~ √n 인 약수
b = √n보다 큰 약수
ex) 24의 (1과 자기 자신을 제외한) 약수는 2, 3, 4, 6, 8, 12
√24 = 4.x이므로, a는 2, 3, 4가 될 수 있고 그 a에 해당하는 b는 √24보다 큰 6, 8, 12가 된다.

 

따라서, √n 까지만 검사를 해보면 된다.

이를 코드로 나타내면 다음과 같으며, 시간복잡도는 O(√n)이다.

n이 1억이라고 하면 앞서 두 코드들은 1억 번이지만,

이 코드는 1만 번으로 훨씬 효율이 좋다는 것을 알 수 있다.

public class Main
{
	public static void main(String[] args) {
		int n = 3;
		if (isPrime(n)) {
		    System.out.println("소수군요!");
		} else {
		    System.out.println("합성수군요!");
		}
	}
	
	private static boolean isPrime(int n) {
	    if (n < 2) {
	        return false;
	    }
	    
	    for (int i = 2; i * i <= n; i++) {
	        if (n % i == 0) {
	            return false;
	        }
	    }
	    
	    return true;
	}
}

 

📝  1부터 n까지 모든 소수 구하기

어떤 수 n이 소수인지 아닌지 알아내는 데 걸리는 시간복잡도는 O(√n)이었다.

n = 백만인 경우: √n = 1,000

n = 1억인 경우: √n = 10,000

 

그럼, 1부터 n까지의 모든 소수를 구하는 데 걸리는 시간복잡도는 몇 일까?

각각의 수에 대해서 소수인지 아닌지를 검사해야 하므로,

각각의 수에 대해서 O(√n) 만큼의 시간이 걸리며 수는 총 n개가 있으므로, O(n√n)이 걸린다.

n = 백만이라면 1,000,000 * 1000 = 1,000,000,000 = 10억 = 10초

 

너무 많은 시간이 걸린다!

 

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

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

2의 배수(2를 제외한), 3의 배수(3을 제외한), 5의 배수(5를 제외한) 등의 순서로 수를 지워나가는 것으로

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

 

 

👆 아아...이것은 『체』라는 것이다....

 

에라토스테네스의 체로 1부터 50까지의 수에서 소수를 걸러내 보자!

 

> 일단 1부터 50까지 숫자를 쭉 쓴다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

> 1은 소수도 합성수도 아니므로, 가장 먼저 1을 지운다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

> 2를 제외한 2의 배수를 지운다.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

> 3을 제외한 3의 배수를 지운다.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

> 4의 배수는 2의 배수에서 이미 지워졌기 때문에, 5를 제외한 5의 배수를 지운다.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

> 7을 제외한 7의 배수를 지운다.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

헉헉...그렇다면 언제까지 지워나가야 하는 걸까?

 

에라토스테네스의 체를 이용해 1 ~ n까지의 소수를 알고 싶다면, √n 이하의 수의 배수까지만 지우면 된다.

√n 이하의 수의 배수만 체크해도, 소수가 아닌 수는 전부 지워진다!

 

위의 예제에서 50의 제곱근은 7 이상 8 미만이므로, 7의 배수까지만 지워나가면 된다.

 

다시 정리하자면,

1부터 n까지 범위 안에 들어가는 모든 소수를 구하려면, '에라토스테네스의 체'를 사용한다.

① 2부터 n까지 모든 수를 써놓는다.

② 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

③ 그 수는 소수이다.

④ 이제 그 수의 배수를 모두 지운다.

 

50까지의 소수를 구한다고 할 때, 8의 배수는 이미

2, 3, 5, 7로 인해서 지워져 있다!!

8 * 2 : 2의 배수
8 * 3 : 3의 배수
8 * 4 : 2의 배수
8 * 5 : 5의 배수
8 * 6 : 2의 배수
8 * 7 : 7의 배수

 

8 * 8은 64로 50을 넘기 때문에, 더 이상 수행할 필요가 없다.

남아있는 모든 수가 소수이다.

 

이를 코드로 나타내면 다음과 같다.

이때, 안쪽 for문의 j 초기값을 i * i부터 시작하는 이유는

i * i 보다 작은 수는 이미 이전의 소수들에 의해 제거되었기 때문이다.

 

예를 들어, i가 3일 때 j가 6부터 시작하게 된다면, 6은 2의 배수로 이미 제거되었을 것이다.

따라서, 초기값을 i * i로 설정함으로써 이전에 이미 제거된 수들을 효과적으로 건너뛰고 중복을 방지할 수 있다.

 

다만, n의 크기에 따라서, i + i 혹은 i * 2로 변경하는 것이 좋다.

예를 들어, i가 백만인 경우 i * i는 범위를 넘어가기 때문에 정수오버플로우를 방지하기 위함이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> primeList = doSieveOfEratosthenes(n);
        for (int prime : primeList) {
            System.out.print(prime + " ");
        }
    }

    private static ArrayList<Integer> doSieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];

        // 모든 수를 소수로 가정
        Arrays.fill(isPrime, true);

        // 에라토스테네스의 체 알고리즘 적용
        for (int p = 2; p * p <= n; p++) {
            // isPrime[p]가 true이면 p는 소수
            if (isPrime[p]) {
                // p의 배수들은 모두 소수가 아니라고 표시
                for (int multiple = p * p; multiple <= n; multiple += p) {
                    isPrime[multiple] = false;
                }
            }
        }

        // 소수 출력
        ArrayList<Integer> primeList = new ArrayList<>(); // 소수 저장용
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }

        return primeList;
    }
}