프로그래머스 (2) 썸네일형 리스트형 [프로그래머스] Lv1) 소수 찾기 ( 에라토스테네스의 체, 소수 찾기 ) 1 부터 n 까지의 수 중에서 소수의 개수를 반환하는 문제 입니다이전 Lv1) 기사단원의 무기 문제에서 사용한 에라토스테네스의 체를 다시 이용하면 됩니다. function solution(n) {// idx 자체를 값으로 사용하기 위해 let isPrime = new Array(n + 1).fill(true); isPrime[0] = isPrime[1] = false;// 제곱근 까지만 계산 for (let i = 2; i * i e === true).length;} 제곱근 까지만 계산하는 이유는 아래 링크에 설명 되어있습니다.https://daunje0.tistory.com/135 limit ? power : e).reduce((a,b) => a+b);}이 코드는 시간복잡도가 O.. [프로그래머스] Lv1) 기사단원의 무기 ( 에라토스테네스의 체, 소수 , 약수 찾기 ) 이 문제는 약수 찾기의 문제입니다function solution(number, limit, power) { let arr = [] let count = 0 for(let i = 1; i e > limit ? power : e).reduce((a,b) => a+b);}이 코드는 시간복잡도가 O(n^2)이기에 시간초과로 fail 이 된 경우 입니다.시간 복잡도를 줄이기 위해서는 에라토스테네스의 체를 이용해야한는 것을 검색을 통해 힌트를 얻었습니다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두.. 이전 1 다음
