프로그래머스 Lv.1 : 소수 찾기★

문제

프로그래머스 문제

내 풀이

• 처음 풀이는 정확성만 맞고 효율성 0점이어서..^^.. 남의 도움을 받아야만 했다. ▽ 남의 도움
• 어떤 자연수 n이 있을 때, √n 보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수입니다.
  언뜻 이해하기 힘들겠지만 한 번 이해하면 쉽습니다. 증명을 생략하고 예를 들겠습니다. 먼저 101이 소수인지 아닌지 판별하기 위해서 우리는 √101을 구하면 10.xxx이 됩니다. 자 10보다 작은 소수는 뭐가 있을까요? 일단 2, 3, 5, 7이 있습니다. 그런데 딱 봐도 이 4개의 소수로만 101이 나누어 떨어지지 않습니다. 그러므로 101소수입니다. 위의 방식을 이용하면 25개의 소수를 모두 이용해야 하지만 지금은 4개만 이용해도 쉽게 계산이 됩니다.

function solution(n) {
    let answer = 1;
    if(n === 2) return answer;
    const numbers = Array(Math.ceil(n/2)-1).fill(3).map((num, idx) => num + 2 * idx);
    
    for (number of numbers){
        answer++;
        for(var i=3; i * i <= number; i += 2) {
            //console.log(`${number} % ${i} === ${number % i}`);
            if(number % i === 0) {
                answer--;
                break;
            }

        }         
    }
    
    return answer;

}