// trial 1 // 효율성 시간 초과 function solution2(n) { var answer = 0; if (n > 2) { let i = 3; while (i <= n) { isPrime(i) && answer++; i++; } return ++answer; //n이 2일 때 } return 1; } function isPrime(n) { let i = 2; while (i <= Math.sqrt(n)) { if (n % i === 0) return false; i++; } return true; } /* isPrime 2 ~ sqrt값까지 약수인지 판별 solution2 입력값이 2부터 주어지므로, 2일 경우 1을 return하고 n이 3일 때부터는, 3부터 n까지 소수인지 판별해 소수일 경우, answer를 증가시킴. 이 경우, n까지의 정수에 대해 매번 isPrime을 실행하므로 효율성이 꽝. */ //trial 2 //효율성 시간 초과 function solution2(n) { if (n === 2) { return 1; } if (n === 3) { return 2; } if (n <= 5) { return 3; } if (n <= 7) { return 4; } let answer = 4; for (let i = 11; i <= n; i += 2) { if (i % 3 == 0) continue; if (i % 5 == 0) continue; if (i % 7 == 0) continue; if (isPrime(i)) { answer += 1; } } return answer; } /* 2,3,5,7까지의 n에 대해 구해진 결과를 리턴하고, 11부터 홀수에 대해서만 소수를 판별해 소수 판별 시행을 줄여봄. 3, 5, 7의 배수일 경우 소수 판별 없이 다음 정수로 넘어감. */ //trial 3 // 효율성 통과 function solution2(n) { let answer = 0; const primeArr = Array(n + 1).fill(1); //인덱스와 정수를 일치시키기 위해 n+1 array 생성 primeArr[0] = 0; primeArr[1] = 0; //prime이 아닌 0,1은 0으로 체크 fillPrimeArr(2, primeArr); fillPrimeArr(3, primeArr); fillPrimeArr(5, primeArr); fillPrimeArr(7, primeArr); for (let i = 11; i <= Math.sqrt(n); i += 2) { //11부터 홀수가 prime일 경우, fillPrime 시행 if (i % 3 === 0) continue; if (i % 5 === 0) continue; if (i % 7 === 0) continue; isPrime(i) && fillPrimeArr(i, primeArr); } for (let tf of primeArr) { tf && answer++; } return answer; } function isPrime(num) { for (let i = 11; i <= Math.sqrt(num); i += 2) { if (num % i === 0) return false; } return true; } function fillPrimeArr(prime, arr) { for (let i = prime * 2; i < arr.length; i += prime) { arr[i] = 0; //prime은 1로 남기고 prime의 배수는 모두 0으로 체크 } } function othersSolution2(n) { const s = new Set(); for (let i = 1; i <= n; i += 2) { s.add(i); } s.delete(1); s.add(2); // 2,3,5,7,9,11,13,... 2와 n이하의 홀수 for (let j = 3; j < Math.sqrt(n); j++) { if (s.has(j)) { for (let k = j * 2; k <= n; k += j) { s.delete(k); } //소수의 배수를 모두 지움. } } return s.size; } // trial 3와 반대 방식으로 푼 풀이 // set을 사용 지니어스.. // 먼저 채우고 // set에 포함되었을 경우, delete function solution2(n) { let s = [...Array(n).keys()]; // [0,1,2,3,4,5,...,n-1,n] // console.log(s); s[0] = 0; for (let i = 2; i <= parseInt(n ** 0.5) + 1; i++) { // console.log(i); for (let j = 2; j <= (n - i) / i + 1; j++) { // j <= n/i s[i * j - 1] = 0; } } return s.filter((x) => Boolean(x)).length; }