10001번째의 소수
문제
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.
풀이 (본인)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| function numberOfPrime(n) { var countPrime = 0; for(var num = 1; num < Number.MAX_VALUE; num++){ var count = 0; for(var innerNum = 1; innerNum<=num; innerNum++){ if(num%innerNum===0){ count++; } } if(count === 2){ countPrime++; } if(countPrime === n){ return num; break; } } } console.log(numberOfPrime(10001));
|
풀이 (본인 개선 코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| var num = 2; var priCnt = 0; while(num){ var priNum = true; for(var divNum = 2; divNum < num; divNum++){ if(num%divNum === 0){ priNum = false; break; } } if(priNum){ priCnt++ } if(priCnt === 10001){ console.log(num) break } num++ }
|
배운점
- 소수 코드를 작성 할 때 1과 자기자신만 나눠지는 수를 소수로 생각하여 나머지(%)가 0인 함수를 찾아 개수가 2개일때만 소수로 판별하는 함수를 작성 하였는데 코드 실행 속도가 너무 오래 걸려 개선하였다.(10배정도 속도가 빨라짐.)
- count 대신 boolean타입으로 소수 구별하는 방법을 잘 사용해야겠다.