[프로그래머스] level1. 소수찾기 ( javascript)

문제

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

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

의식의 흐름

소수 찾는 법을 모르겠다.

다른 이들의 정답

방법1.

 

function solution(n) {
    var arr = [];
    var cnt = 0;
    for (var i = 0; i < n + 1; i++) {
        arr.push(true);
    }

    for (var i = 2; i * i <= n; i++) {
        if (arr[i]) {
            for (var j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    arr.splice(0, 2, false, false);
    for(var i = 0; i <arr.length; i++) {
        if(arr[i]) cnt++;
    }

    return cnt++;
}

참조 : 블로그

 

수학적 이해가 필요하다.
왜 제곱근n까지만 검사해도 되는지 이해하고,
왜 검사를 제곱근n까지만 하는지 => 시간복잡도 O(n) > O(sqrtn) >O(logn)개념
여기서는 제곱근 대신 제곱을 사용하였다.

 

방법2.

 

function numberOfPrime(n) {
    var result = 0;
    // 함수를 완성하세요.
    var cnt=0;
    for(var a=2;a<=n;a++){
    cnt=0;
      for(var b=1;b<=a;b++){
            if(a%b==0)
          cnt++;
      }
    if(cnt==2)
      result++;
    }
    return result;
}

 

개인적으로 이것도 깔끔한 것같다.(직관적이라서)
1과 내 자신만 나뉘는 특성을 이용해서 코딩을 하였다.