인프런 커뮤니티 질문&답변

안녕하세요.
다른 분 풀이에서 "에라토스테네스의 체"라는 것이 있어서,
구글링 해보니 포스트에는 최적의 알고리즘 이라는 내용이 있었는데,
실제로 속도 비교를 해보니 오히려 성능이 좋지 않다 라고 느꼈습니다.

두 알고리즘에 사용된 소수의 특징 은 다음과 같았습니다.

1. 1은 소수가 아니다. (해당 값일 경우 바로 중단)
2. 2는 무조건 소수이다. (해당 값일 경우 바로 중단)
3. 4 이상의 수는 Math.sqrt 까지만 그 값을 반복한다.
문제 풀이에 2가지 쟁점을 잡아 풀었습니다.
3-1. 3번 알고리즘을 사용하기 위하여, 2와 4 사이의 유일한 정수인 3은 소수이므로 바로 중단한다

함수를 실행한 파일

 

성능 비교 (결과값은 모두 동일하게 출력)

 

기본 풀이 방법 코드

22-javascript-coding-test/2.Prime_numbers_basic.js at main · unchaptered/22-javascript-coding-test (github.com)

에라토스테네스의 체
22-javascript-coding-test/2.Prime_numbers_adv.js at main · unchaptered/22-javascript-coding-test (github.com)

에라토스테네스의 체에서 몇 가지 개선점이 상상되기는 하지만,
테스트할 수가 클수록 그 만큼 배열을 생성하는 데 걸리는 시간 이 길어지는 단점이 보이는데, 어째서 해당 알고리즘이 성능적으로 좋은지 모르겠습니다.

아니면 제가 Array.prototype.filter() 를 통해서 새로운 배열을 만들고 있기 떄문에 성능 저하 가 발생하고 있는 것일까요?

p.s. 강의 파일과 관련있는 코드라서 강사님 답변 받고 나면 바로 private 으로 돌려놓겠습니다.
p.p.s 이 부분은 궁금해서 커뮤니티 같은데에 질문을 남겨서 의견을 받아도 될까요? ㅠㅠ