TIL_026_210311
소수(Prime Number) 구하기
알고리즘 문제에서 종종 등장하는 소수 구하는 로직은 국룰처럼 알고 있으면 좋다.
소수란 약수가 1과 자기자신뿐인 자연수를 뜻한다. (자연수란 1이상의 양의 정수)
즉, 변수가 소수인지 판별하려면 2부터 시작해서 변수-1까지 나누어 떨어지는 지 확인하면 된다.
나누어 떨어지면 나눈 수 역시 약수가 되므로 1과 자기자신 외에 또하나의 약수가 있으므로 소수가 아니게 된다.
나누어 떨어진다는 것을 코드로 표현하면 "변수 % i === 0"으로 나눈 나머지가 0이면 그 의미가 같다.
그런데 2부터 변수-1까지가 아니라의 변수/2 까지만 나눠봐도 된다.
예를 들어, 13이 소수인지 판별하려고 할 때, 13/2,13/3,13/4,13/5,13/6 에서 나누어 떨어지는 게 없으면 굳이 13/7인지를 확인할 필요가 없다. 소수가 아닌 12를 예를 들면 12/7~12/11은 결코 나누어 떨어질 수 없다.
이 논리를 코드로 표현해보면 아래와 같다.
const isPrime = function(number) { if(number <= 5) { if(number === 2 || number === 3 || number === 5) return true; else return false; } for(let i = 2; i < number / 2; i++) { if(number % i === 0) return false; // 나누어 떨어지면 소수가 아니다. } return true; // 2부터 변수의 절반까지 모두 나눠봤을 때 }
아주 기초적인 알고리즘이니 숙지해두자.
Author And Source
이 문제에 관하여(TIL_026_210311), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rjc1704/TIL026210311저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)