소수(Prime number) 정복하기

Sheryl Yun·2022년 6월 7일

기타

알고리즘 & 자료구조

목록 보기

1/3

이틀에 걸쳐 겨우 이해한 소수 씨(^-^)에 대해 정리한 글입니다.
노션에 작성한 걸 그대로 들고왔더니 중간중간에 곱하기 연산자(*)가
생략된 경우가 종종 있어요. 왜 수정이 되지 않는 걸까나 🙄

소수란?

1을 제외하고, 1과 자기 자신으로만 나누어지는 수

소수를 구할 때 제곱근을 활용하는 이유

"n의 약수는 무조건 sqrt(N)의 범위 내에 존재한다."

4의 약수는 1 4, 2 2, 4 * 1 이렇게 3가지 경우로 구할 수 있다.

25의 약수는 1 25, 5 5 이렇게 2가지 경우로 구할 수 있다.

즉, n(4, 25)의 제곱근(2, 5)까지 구하면 그 뒤로는 몫과 나누는 값만 반대로 된다.

따라서 어떤 수의 배수가 되지 않는 소수를 구하려면

n의 제곱근까지만 따져서 배수가 아닌 경우만 구하면 된다.

⇒ 시간복잡도: O(sqrt(n))

에라토스테네스의 체

"모든 배수들을 다 지워나가면 나머지는 전부 소수이다."

소수의 배수는 무조건 해당 소수를 곱해지는 값(약수)으로 포함한다.

소수란 어떤 수의 ‘배수’가 아닌 수를 말하므로,

따라서 소수의 배수는 절대로 소수가 될 수 없다.

에라토스테네스의 체는 마치 체를 거르는 것처럼

소수의 배수들을 지워나가면서 소수를 구하는 방법이다.

예를 들어 가장 작은 소수인 2는 건너뛰고 2의 배수를 다 지운 뒤

남은 수 중에서 2의 다음 소수인 3은 건너뛰고 3의 배수를 또 지워나가는 식이다.

여기서 주의할 것은

n이 100일 때 n까지의 범위 내의 소수를 구한다고 하면

배수를 지우는 반복문은 100의 제곱근인 10까지만 돌리면 된다.

배수를 지우는 j 반복문은 i의 배수부터 시작하는데,

11의 배수는 121이므로 이미 100(n)을 초과하여 연산할 필요가 없다.

소수를 구하는 코드

true로 채워진 n + 1 길이의 배열을 만들되 (⇒ Array(n + 1).fill(true) )

0번째와 1번째는 false로 채운다. (⇒ .fill(false, 0 , 2) )
```
function solution(n) {
	let arr = Array(n + 1).fill(true).fill(false, 0 , 2);
}
```
n의 길이가 아닌 n+1의 길이를 생성하는 이유?

n까지의 숫자판을 구현하기 위해 index를 각 숫자 요소로 이용할 것인데,

n까지로 길이를 잡으면 n이 3일 때는 0, 1, 2로 2까지만 숫자가 생성된다.

즉, n + 1을 해야 숫자(3)까지를 이용할 수 있다.

(앞의 0, 1은 for문을 돌 때 아예 건너뛸 것이기 때문에 고려하지 않음)

소수의 배수를 제거하는 반복문을 만든다. (이때 0, 1을 건너뛰어 i를 2부터 돈다)
- 배열의 각 인덱스를 탐색하면서
- 각 소수(i)는 놔두고, 소수의 배수(j = i * i)부터
- j에 i를 더해가며(j += i)
- arr의 j 자리를 false로 바꾼다.

     // n의 제곱근 범위(i * i ≤ n 또는 i ≤ Math.sqrt(n))까지만 연산 (가독성이 더 좋은 전자로 진행)
     for (let i = 2;  * i <= n; i++) {
     	// arr[i]가 true일 때만 연산 => 이미 false인 인덱스들은 건너뛰도록 분기화
     	if (arr[i]) {
     		// i의 제곱수(i * i)부터 시작, 이후 j에 i값을 더해가며 반복하면 i의 모든 '배수'를 제거한다.
     		for (let j = i * i; j <= n; j += i) {
     			arr[j] = false;
     		}
     	}
     }

j를 i * i부터 시작하는 이유?

j가 5라고 했을 때 25부터 시작하는데,
그 앞의 수들은 이미 모두 소수의 ‘배수’로 판별된 상태이다.
(i가 2, 3, 4였을 때 ⇒ 10(= 2 5), 15(= 3 5), 20(= 4 * 5)으로 각각 2, 3, 4의 배수로서 모두 제거됨)
그래서 이미 다 false 처리가 되었기 때문에 앞부분은 다 건너뛰고 25부터 시작하는 것이다.

증감식에서 j += i 를 하는 이유?

소수인 i가 곱해져서 만들어지는 모든 수는 ‘소수의 배수’이다.
예를 들어 i가 2일 때 j 값은 2 * 2 = 4 부터 시작하고,
j + i 인 값, 즉 4 + 2 = 6, 6 + 2 = 8, … 은 모두 i(2)의 배수이므로 false로 제거된다.
⇒ 즉, 각 소수(i)의 제곱인 수(4, 9, 16, 25, …)부터 시작하여 이후에 등장하는 모든 소수의 배수들을 제거하게 된다.