소수 (Prime number)
소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.
정수론에서 매우 중요한 주제이며, 특히 현대사회에서 암호학에서 많이 사용하여서 매우 중요해졌다.
출처: 위키백과
소수 판별하기 (JavaScript)
소수를 판별하는 방법은 여러가지가 있다. 그 중 아래의 두가지를 소개한다.
이 판별법은 입력값이 소수인지 아닌지를 판별하는 방법이다.
이를 응용해서 소수의 개수를 구할수도 있다.
- 반복문 (제곱근으로 최적화 가능)
- 에라토스테네스의 체
1. 반복문
1) 가장 기본적인 방법으로 반복문을 수행하면서 1이외의 수로 나누어 떨어지지 않는지 확인한다.
이때 시간복잡도는 O(n)이 된다.
function isPrime(num) {
if(num === 1) return false; //1은 소수가 아니다.
// 1과 자기자신을 제외하고 반복문을 수행하도록 한다.
for(let i = 2; i < num; i++) {
if(num % i === 0) return false;
//num이 다른 수로 나눠떨어진다면 소수가 아니다.
}
return true; //반복문을 종료할때까지 if문이 실행되지 않았다면 소수이다.
}2) 반복문 최적화 1 - num의 절반만 반복하기
num의 약수는 절반을 넘을 수 없기때문에 반복수행을 줄일 수 있다. 시간복잡도는 O(n)이다.
function isPrime(num) {
if(num === 1) return false;
// 반복문 수행 횟수를 줄였다
for(let i = 2; i <= num / 2; i++) {
if(num % i === 0) return false;
}
return true;
}
3) 반복문 최적화 2 - num의 제곱근까지만 반복하기
num의 약수는 짝으로 존재한다. 아래 그림의 예처럼 쌍을 이루는 약수 중 하나만 찾으면 나머지는 확인하지 않아도 된다.
그러므로 제곱근까지만 확인하면 된다. 이렇게 하면 반복횟수를 더 많이 줄일 수 있다. 시간복잡도는 O(√n ) 이 된다.
function isPrime(num) {
if(num === 1) return false;
// Math.sqrt 함수를 사용하여 제곱근까지만 반복하도록 한다.
for(let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
if(num % i === 0) return false;
}
return true;
}
2. 에라토스테네스의 체
에라토스테네스의 체는 소수를 찾는 방법으로 고대 수학자 에라토스테네스가 발견하였다.
프로그래밍 대회에서 소수 찾기시 가장 자주 사용되는 방법중 하나이다.
알고리즘은 아래와 같다 (출처: 위키피디아)
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
즉, num까지의 수에서 2부터 num의 제곱근까지 반복하면서 해당 수의 배수를 지우고 남는 수를 구하는 것이다.
자바스크립트로 구현 (1~num까지 범위에서 소수 갯수 구하기)
: 배열을 true로 채운 후 소수가 아닌 요소는 false로 바꾸고, 마지막에 배열내 true인 요소의 수를 구한다.
function isPrime(num) {
let arr = Array(num + 1).fill(true);
//index 0이 존재하므로 배열을 num + 1로 만든다.
arr[0] = false;
arr[1] = false;
//배열의 index 0과 1은 소수가 아니므로 false로 만든다.
for(let i = 2; i * i <= num; i++) { //제곱근까지만 반복
if(arr[i]) {
for(let j = i * i; j <= num; j += i) {
//반복을 i * i 부터 시작하는 것은 그 이전의 값은 j이전의 수에서 이미 확인했기 때문
arr[j] = false; //배수이므로 소수가 아닌것으로 만든다.
}
}
}
return arr.filter(el => el).length //filter로 arr중 값이 true인 것의 개수를 구한다.
}
Reference
1) https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)
3) https://loosie.tistory.com/267
5) https://ant-programmer.tistory.com/2
댓글