PR - 소수찾기[실패]

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)


예시

nresult
104
53

풀이

  • 2부터 n 까지 순회하면서 isPrime 함수에 i를 넣고 실행한다.
  • isPrime 함수 안에서는 2부터 i 의 제곱근까지 순회하면서 i가 다른 자연수로 나누어 떨어지는지 검사하고, 나누어 떨어지면 false , 아니면 true를 반환한다.

코드

function solution(n) {

    let answer = 0;

    for(let i = 2; i <= n; i++) {
        if(isPrime(i)) answer++; 
    }
    return answer;
}

function isPrime(n) {
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) return false;
    }
    return true; 
}

회고

정확성은 100점인데 효율성이 0점이 나오는 걸 보면
시간복잡도를 좀 더 줄여야 하나보다.

좋은 웹페이지 즐겨찾기