문제 조건 분석

입력: 수 개수(N), 숫자들
출력: 소수 개수

설계

소수는 1과 자기 자신을 뺀 나머지 수들로 나누어지지 않는 경우
- 따라서 입력받은 수를 순회하며 1과 자기자신 외에 나머지가 0인 경우 소수가 아니라는 조건 걸기

트러블슈팅

return 문 누락

메인 함수 반환값이 누락돼서 추가했습니다. 이런 기본적인 실수는 하지 않도록 처음 코드 작성할 때 틀부터 잘 작성하고 들어가야겠다고 생각했습니다.

다른 풀이

반복문 - 최적화 버전

기본적으로는 내 풀이와 같은 접근
내 풀이는 시간복잡도는 O(n)
최적화 방법 1 - num의 절반만 반복
- 시간복잡도 O(n)
- 약수는 그 수의 절반을 넘을 수 없는 원리
최적화 방법 2- num 제곱근까지만 반복
- 약수는 짝으로 존재한다. 쌍을 이루는 약수 중에 하나만 찾으면 나머지는 확인할 필요가 없다.
- 따라서 제곱근까지만 확인하면 된다
- 시간복잡도 O(√n)

에라토스테네스의 체

소수 찾는 방법으로, num까지의 수에서 2~num 제곱근까지 반복하며 해당 수 배수를 지워 남는 수를 걸러내는 것
시간 복잡도 O(N * log log N) : 조화급수(역수들의 합)와 연관이 있는데 이 부분이 log logn 정도라고 한다.
에라토스테네스의 체로 풀이한 예시

function isPrime(num) {
	let arr = Array(num + 1).fill(true);
    //index 0이 존재하므로 배열을 num + 1로 만든다.

    arr[0] = false;
    arr[1] = false;
    //배열의 index 0과 1은 소수가 아니므로 false로 만든다.

    for(let i = 2; i * i <= num; i++) { //제곱근까지만 반복
        if(arr[i]) {
            for(let j = i * i; j <= num; j += i) {
                //반복을 i * i 부터 시작하는 것은 그 이전의 값은 j이전의 수에서 이미 확인했기 때문
                arr[j] = false; //배수이므로 소수가 아닌것으로 만든다.
            }
        }
    }
    return arr.filter(el => el).length //filter로 arr중 값이 true인 것의 개수를 구한다.
}

참고자료

소수 구하기