소수(Prime number) 판별법/ javaScript

소수 (Prime number) 판별법

소수란 1, -1과 자기 자신, 자기 자신의 반수로 밖에 나누어 떨어지지 않는 1 이외의 정수, 즉 양의 약수가 2개인 자연수를 의미한다.

소수는 다양한 알고리즘 문제에 자주 등장하는 개념이다. 그러므로 소수를 판별하는 법을 알아두고, 효율적인 방법을 기억해두는 것이 좋다.

 

1. 3부터 자기 자신까지 비교

첫 번째 방법은 말 그대로 3부터 자기 자신까지 모든 수를 숫자에 나누어보아 약수 여부를 판단하는 것이다. 아래 코드를 보자

const isPrime =  ( num ) => {
    if(num < 2)     return false;	// 0과 1은 소수가 아니다.
    if(num === 2)   return true;	// 2는 유일한 짝수인 소수이다.
    if(num % 2 === 0) return false; // 짝수는 미리 판별한다.
    
    // 3이후 숫자를 num과 나눈 나머지로 약수 여부를 확인한다.
    for(let i = 3; i < num; i += 2){
        if(num % i === 0) return false;
    }
    
    //약수가 윗 범위에 없다면 소수이다.
    return true;
}

 

위 코드를 통해 가장 직관적인 방법으로 소수를 판별할 수 있다. 하지만 숫자가 커질 수록 많은 연산을 필요로 하여 효율적이지 못하다.

 

2. 자신의 제곱근까지만 확인하기

윗의 과정에서 판별할 때 불필요한 부분을 제거한다면 연산의 수가 줄어들 수 있다.

판별 숫자를 n 이라 한다면 약수는 n = a * b(a <= b라 가정) 라고 할 수 있다. 이 과정에서 a와 b의 차이가 최소로 날 때 그 값은 √n*√n = n 이 나온다.

따라서 n이 a * b로 표현될 수 있고, a <= b일 때, b의 최소값이며 a의 최대값은 √n이다.

• a가 √n보다 크게 되면, a * b > n
• b가 √n보다 작게 되면, a * b < n
• 따라서 a <= b일 때, a <= √n, b >=√n이다.
  a와 b의 차이가 가장 작은 경우는 a와 b가 서로 √n이 되는 경우이다. 그러므로 √n까지만 반복해보면 이 수가 소수인지 알 수 있다.

위의 말을 예를 들어 쉽게 설명하자면 다음과 같다.

 n = 36이라고 가정해보자.
36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 이다.
이는 1x36, 2x18, 3x12, 4x9, 6x6의 결과이다.
이들은 반비례 관계로 몫이 커지면 나누는 값이 작아지거나, 나누는 값이 커지면 몫이 작아진다. n의 절반(제곱근)까지 계산하게 되면 이후 몫과 나누는 값은 반대로 바뀐다.

 

따라서 n의 제곱근까지, 그러니까 a와 b가 서로 √n이 될 때 까지만 반복해보면 이 수가 소수인지 알 수 있다.

 

const isPrime =  ( num ) => {
    if(num < 2)     return false;
    if(num === 2)   return true;
    if(num % 2 === 0) return false;
    
    for(let i = 3; i <= Math.sqrt(num); i += 2){
        if(num % i === 0) return false;
    }
    
    return true;
}

 

3. n이하의 숫자 중 소수의 개수 찾기 (에라토스테네스의 체)

단순 소수를 판별하는 것이 아닌 일정 범위에서 소수의 개수를 찾을 경우, 모든 숫자를 위 판별식으로 판별한다면 많은 리소스를 사용하게 될 것이다. 그렇기에 더욱 효율적인 방법이 필요하다.

 

그 방법이 에라토스테네스의 체이다.

 

1을 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리

 

아래는 나무위키에서 제공한 에라토스테네스의 체를 쉽게 이해할 수 있는 이미지이다.

출처 : 나무 위키

function solution(n) {
    const arr = [];
    
    // 인덱스 번호가 주어진 숫자 n과 대응하도록 
		// 빈 배열을 만들고 원소는 true 값으로 채워준다.
  	// 여기서 true 는 소수라는 의미이다.
		// 배열은 0부터 시작하므로, 주어진 숫자 n에 1을 더해준다.
    for (let i = 0; i < n + 1; i += 1) {
        arr.push(true);
    }
    
    // 주어진 수의 제곱근까지만 계산해서 불필요한 반복을 최소화한다.
    // arr[i] 가 소수일 경우, 반복문을 진행한다.
    // 맨 처음 시작하는 2는 소수이므로,
    // 2를 제외한 2의 제곱부터, 제곱 값만 체크하여 지워나간다.
  	// 제곱근까지 반복한다.
    for (let i = 2; i * i <= n; i += 1) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    
  	// 0과 1은 소수가 아니므로 false 값으로 바꿔준다.
    arr.splice(0, 2, false, false);
    
  	// 배열에서 true인 값만 걸러내고, true인 값의 개수를 출력한다.
    const result = arr.filter((value) => {
        return value !== false;
    })
    
    return result.length;
}