(JavaScript) 정수론 - 소수 판별하기
소수란 1보다 큰 자연수중 1과 자기자신만을 약수로 가지는 수 이다. 즉 1과 자기 자신 외의 어떤 수로도 나누어떨어지지 않는다.
소수를 구하는 가장 간단한 방법은 1부터 자기자신까지 모든 수로 나누어 보는것이다. 그때 나누어떨어지는 수가 있으면 소수가 아닌것이다.
하지만 이러한 완전탐색방식을 사용하면 O(N)의 시간복잡도로 꽤 긴시간이 걸리게 된다.
수학적 원리를 이용한 알고리즘을 활용하면 소수를 탐색하는 시간을 줄일 수 있다.
1. 소수 탐색의 기본 조건
프로그래밍으로 소수를 탐색하면 반복문을 활용하게 된다. 반복문으로 특정 범위에서 소스를 탐색하기에 앞서 기본적으로 고려해야할 조건이 있다.
- 1은 소수가 아니다.
- 2는 소수이며 2의 배수는 모두 소수가 아니다. (2가 약수이므로)
소수를 탐색하기에 앞서 두 조건을 고려하면 반복문을 만들기가 보다 수월해지고 탐색해야할 수 자체가 많이 감소한다.
2. 소수를 판별할때는 제곱근까지 : O(√N)
16이 소수인지 판별하는 과정을 살펴보자.
- 16이 소수이려면 1과 16 이외에 약수가 없어야한다.
- 약수가 존재하는지 알아보기위해 2~15의 수로 16을 나누어본다.
- 1과 16외에 2, 4, 8이 16의 약수이므로 16은 소수가 아니다.
여기서 16의 소수판별을 위해서는 2~15 범위인 총 14번의 나눗셈 계산이 필요하다. 숫자가 커지면 계산해야할 수도 따라서 많아진다.
그런데 효율적인 판별을 위해서는 해당 수의 제곱근 까지만 계산하면된다. 예를들어 16이 소수인지 판별하고싶으면 4까지만 계산해보면 되는것이다. 왜일까?
- 16의 약수쌍을 정리해보면 아래와 같다.
| 1 | 16 |
| 2 | 8 |
| 4 | 4 |
| 8 | 2 |
| 16 | 1 |
- 여기서 작은 쪽 약수를(1, 2, 4, 2, 1) 보면 모두 16의 제곱근(4) 이하이다.
- 판별하려는 수의 제곱근은 약수쌍이 같은수 (4, 4)이다. 제곱근보다 큰 수(8)의 약수쌍은 제곱근보다 작은수(2)가 될 수 밖에 없다.
- 따라서 제곱근까지만 나눗셈 계산하면 그 이후 약수도 자동으로 걸러진다.
2-1. 왜 효율적인가?
소수 판별 알고리즘을 만들때는 보통 약수 하나를 발견하는순간 반복문을 종료한다. 예를들어 16이 소수인지 판별할때는 전체 수를 반복하든 제곱근까지 반복하든 약수인 2를 발견하면 반복문이 즉시 종료되므로 소요시간에 차이가 없다.
제곱근까지만 연산하는것은 판별하려는 수가 소수일때 매우 효율적이다. 예를들어 97을 판별한다면
- 모든 수를 연산할 경우
2~96사이 약수가 없으므로 모든 수를 나눗셈 연산한다. O(N)의 시간복잡도이다. - 제곱근까지만 연산할 경우
√97 ≈ 9 이므로 2~9까지의 수만 연산하면 된다. O(√N)으로 실행시간을 단축했다.
3. 에라토스테네스의 체 : O(N log log N)
고대 그리스 수학자 에라토스테네스가 만들어낸 소수판별법이다. 체로 걸러내듯이 소수를 판별하여 에라토스테네스의 체 라고 부른다.
N까지의 범위중 소수를 찾을때 기본적인 원리는 다음과 같다.
- N까지의 수를 테이블에 모두 작성한다.
- 소수도, 합성수도 아닌 수 1을 제거한다.
- 2를 제외한 2의 배수를 제거한다. (2가 약수이므로 소수가 아님)
- 3을 제외한 3의 배수를 제거한다. (3이 약수이므로 소수가 아님)
- 다음 남아있는 수를 찾아 그 배수를 제거한다. (5, 7, 11... 순서로 배수가 제거됨)
- 이를 √N까지 반복하면 소수만 남게된다.
쉽게말해 소수를 점진적으로 찾고 그 소수를 약수로 가지는 수를 모두 제거하는 방식이다. 여기서도 제곱근까지 찾는다는 원리는 동일하게 적용된다.
특정 범위에서 소수를 모두 찾는 상황에서 일반적으로 에라토스테네스의 체는 가장 빠르고 간단한 방법이다.
4. 예제
4-1. 백준 1929번 : 소수 구하기
• 소스코드
const readline = require("readline");
const solution = (input) => {
let [m, n] = input[0].split(" ").map(Number);
let answer = [];
let count = 0;
for (let i = m; i <= n; i++) {
if (i === 1) continue;
if (i === 2) answer.push(2);
if (i % 2 === 0) continue;
count = 0;
for (let j = 3; j <= Math.sqrt(i); j += 2) {
if (i % j === 0) {
count++;
break;
}
}
if (count === 0) answer.push(i);
}
return answer.join("\n");
};
const input = [];
readline
.createInterface({
input: process.stdin,
output: process.stdout,
})
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
console.log(solution(input));
});• 설명
- 범위 m~n 사이의 모든 수에 대해 소수인지 판별한다.
- 먼저 1인경우 연산을 생략한다. (1은 소수가 아님)
- 2인경우 정답배열에 2를 넣는다. (2는 소수)
- 2를 제외한 2의 배수들은 연산을 생략한다.
- Math.sqrt를 통해 수의 제곱근까지만 연산한다. 나눗셈 결과 나머지가 0이면 count값을 증가시키고 반복문을 종료한다.
- count값이 증가되지 않았을경우 소수이므로 정답배열에 해당 수를 넣는다.
4-2. 백준 1456번 : 거의 소수
• 소스코드
const readline = require("readline");
const solution = (input) => {
const [A, B] = input[0].split(" ").map(BigInt);
const limit = 10n ** 7n;
const sieve = new Array(Number(limit + 1n)).fill(true);
const primes = [];
sieve[0] = sieve[1] = false;
for (let i = 2n; i * i <= limit; i++) {
if (sieve[Number(i)]) {
for (let j = i * 2n; j <= limit; j += i) {
sieve[Number(j)] = false;
}
}
}
for (let i = 2n; i <= limit; i++) {
if (sieve[Number(i)]) {
primes.push(i);
}
}
let count = 0;
for (const prime of primes) {
let num = prime * prime;
while (num <= B) {
if (num >= A) count++;
if (num > B / prime) break;
num *= prime;
}
}
return count;
};
const input = [];
readline
.createInterface({
input: process.stdin,
output: process.stdout,
})
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
console.log(solution(input));
});• 설명
- 범위가 매우 크므로 (1~10^14) BigInt를 사용한다.
- 에라토스테네스 체를 사용하기 위해 sieve 배열을 초기화한다. 처음에는 모두 true로 채워져있다.
- 앞서 설명한 에라토스테스트 체의 원리에 따라 소수가 아닌 수를 false로 변경한다.
- 에라토스테네스 체 연산이 완료된후 true인 값들을 primes 배열에 넣는다.
- 문제 조건에 따라 소수들을 범위내에서 거듭제곱하며 조건에 맞는경우 count를 증가시킨다.
- count를 반환한다.
📖 이 글은 학습 과정에서 정리한 내용이라 부족한 점이 있을 수 있습니다.
☑️ 틀린 부분이 있다면 편하게 알려주셔도 괜찮습니다.
😊 읽어주셔서 감사합니다.