소수 찾기

문제 링크

처음 풀이

여기 링크에 소수 찾기 원리가 잘 정리되어 있어서 (소수는 맨날 헷갈리기 때문에) 참고해서 풀었다.

첫 풀이만 참고했더니 시간 초과로 정확도 테스트 10/12, 효율성 테스트 0/4를 통과했다.

function isPrime(n) {
    let isPrime = true;
    
    if (n < 2) isPrime = false;
    if (n % 2 === 0 && n !== 2) isPrime = false;
    for (let i = 3; i < n; i += 2) {
        if (n % i === 0) isPrime = false;
    }
    
    return isPrime;
}

function solution(n) {
    let count = 0;
    
    for (let i = 1; i <= n; i++) {
        if (isPrime(i)) count++;    
    }
    
    return count;
}

새로운 풀이

소수 찾기에서 sqrt를 사용해야 하는 이유는 찾는 범위를 줄여서 실행 시간을 줄이기 위해서이다. sqrt를 추가해서 다시 풀었더니 정확도는 100% 통과했지만 효율성에서 여전히 0% 통과였다.

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

function solution(n) {
    let count = 0;
    
    for (let i = 1; i <= n; i++) {
        if (isPrime(i)) count++;    
    }
    
    return count;
}

생각해보니 isPrime 함수에 넘어온 n이 하나의 조건에만 걸려도 리턴할 boolean 여부 판별이 가능했다. 그래서 isPrime = boolean을 모두 return boolean으로 바꿔주었다.

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

function solution(n) {
    let count = 0;
    
    for (let i = 1; i <= n; i++) {
        if (isPrime(i)) count++;    
    }
    
    return count;
}

훨씬 빨라진 정확도 테스트와 함께 효율성 테스트도 100% 통과했다 👏👏