문제

코드

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

function solution(n) {
    let count = 0;
    // 내가 푼 시간초과 풀이
    for(let i=2; i<=n; i++) {
        let divisor = 0;
        for(let j=2; j<i; j++) {
            if(i%j===0) {
                divisor ++;
                break;
            }
        }
        if(divisor === 0) count++;
    }
    // 제곱근을 이용한 소수판별
    for(let i=2; i<=n; i++) {
        if(isPrime(i)) count++;
    }
    
    return count;
}

내가 푼 1차원적인 2중 for문

• 나름 시간 줄인다고 2부터 시작하는 창의력을 보였지만 숲도 아니고 나무도 아니고 엽록소만 현미경으로 보는 정도의 창의력이었다.
• 수가 커질수록 시간 복잡도가 O(n)이라 초과가 뜸

n/2로 소수 구하기

• 자신의 절반 이상부터는 나눌수가 없다. 따라서 n/2까지만 나머지가 0이 되는지 구한다.
• 이 또한 시간 복잡도가 O(n/2)지만 우리 빅오 형님은 상수따위 개나 줘버리기 때문에 O(n)이다.

제곱근으로 소수 구하기

• 색칠한 애들끼리 곱하면 80이 나오고 약수들의 중간은 대충 루트80 쯤이다.
• 이러면 원래 79번 나눠야하거나 40번 나눠야 할 것을 8번 정도로 확 줄여준다.
• 시간 복잡도는 O(루트N)이다.

참고 사이트

• https://myjamong.tistory.com/139 (소수를 구하는 다양한 방법)