소수란
수학에서
소수라는 것은
1과 자기 자신 이외의
자연수로는 나눌 수 없는 자연수를 의미합니다.
(자연수는 1부터 시작하는 숫자입니다.)
즉 약수를 2개만 가지는 수입니다.
때문에, 1은 소수가 될 수 없죠.
2, 3, 5, 7, 11
의 숫자들이 그에 해당됩니다.
2 = 1과 2로만 나눠짐
17 = 1과 17로만 나눠짐
…
소수 체크
javascript를 활용하여
소수를 판별하는
방법을 확인해 봅시다.
1. 가장 빠른 시간 복잡도를 가지는
제곱근 범위 나누기 법을 활용한
소수 체크 판별식
const isPrime = (number) => {
if(number < 2) return false; // 자연수가 아닌 경우
for(let i = 2; i <= Math.floor(Math.sqrt(number)); i++){
if(number% i === 0){
return false;
}
}
return true;
}* Math.floor() 함수는 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환합니다.
* Math.sqrt() 함수는 숫자의 제곱근을 반환합니다.
한 번, 해석을 해볼까요~?
num % i에서 %는 나머지 값을 구할 수 있는
나머지(%) 연산자입니다.
12를 5로 나누면
몫이 2이고, 나머지가 2이죠.
즉, 12 % 5 = 2가 됩니다.
나머지 연산자를 활용하여,
1과 자기 자신을 제외한
값으로 나누었을 때
나머지가 0인 값이
1개라도 나올 경우,
소수가 아니다
라는 공식을 작성하면 됩니다.
그럼 아래와 같이 표현할 수 있겠네요.
const isPrime = (number) => {
if(number < 2) return false; // 자연수가 아닌 경우
for(let i = 2; i < number; i++){ // 1을 제외하고 2부터 시작하여 자기 자신보다 작은 수
if(number% i === 0){ // 하나라도 나누어 떨어지면 소수가 아님.
return false;
}
}
return true;
}그런데,
제일 위 공식에서는
i <= Math.floor(Math.sqrt(number));
갑자기 제곱근이 나왔습니다.
제곱근(square root)이란,
제곱하여 그 수가 되는 수를 의미합니다!!
제곱근(sqrt) 범위 나누기법으로,
제곱근을 기준으로
그 곱은 대칭적으로 곱이 일어나므로
제곱근 이하의 작은 값까지만 검사를 하면
나머지는 검사를 할 필요가 없다는 방법을 의미합니다.
20이라는 숫자로 예를 들어보겠습니다.
20으로 나누어떨어지는 약수는
1, 2, 4, 5, 10, 20
입니다.
1과 자기 자신을 제외한
2, 4, 5, 10
을 보면,
2는 10과 대칭
4는 5와 대칭됩니다.
20 / 2 = 10;
20 / 10 = 2;
다시 말해
2, 4만 확인하면
굳이 5, 10을 확인하지 않아도
된다는 의미가 됩니다.
20의 제곱근
4.47213595499958....
의 가장 큰 정수를 구하는
Math.floor 함수를 사용하여
2부터 4까지 만 반복하는
반복문을 작성하면 되겠네요.
for(let i = 2; i <= Math.floor(Math.sqrt(number)); i++)
2부터 19까지 18번의 반복문을 돌릴 필요 없이,
2부터 4까지 3번만 확인하면
소수를 판별할 수 있기 때문에
굉장히 효율적이게 됩니다.
const isPrime = (number) => {
if(number < 2) return false; // 자연수가 아닌 경우
for(let i = 2; i <= Math.floor(Math.sqrt(number)); i++){
if(number% i === 0){
return false;
}
}
return true;
}