소수 찾기
문제 프로그래머스 소수 찾기
🔑 Key
소수의 조건은 다음과 같습니다.
- 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수가 소수입니다. 1은 소수가 아닙니다.
- 2는 소수이며 그 이상 2의 배수는 소수가 아닙니다.
- 3은 소수이며 그 이상 3의 배수는 소수가 아닙니다.
소수 판정시 확인 범위
풀이
// 소수 판별 함수
function primeCheck(k){
if(k === 2) return true; // 2는 소수이다.
if(k % 2 === 0) return false; // 2의 배수는 소수가 아니다.
if(k === 3) return true; // 3은 소수이다.
for(let i = 3; i*i <= k; i += 2){ // 3의 배수는 소수가 아니다.
if(k % i === 0) return false; // k의 제곱근까지만 판정
}
return true;
}
function solution(n) {
let answer = 0;
for(let j = 2; j <=n; j++){ // n까지 돌며 j가 소수이면
if(primeCheck(j)) answer++; // answer++
}
return answer;
}