[프로그래머스] 소수 찾기 - JS
문제
문제 자체는 간단했다.
- 2부터 n까지 수를 확인한다.
- 그 수의 루트(sqrt)까지 확인한다.
- n % 루트(sqrt)한 수가 0이면 소수가 아니므로 flag에 기록한다.
처음에는 이러한 방식으로 코드를 짜기 시작했다.
코드 자체는 짜고보니 매우 간단했지만, 효율성 테스트에서는 0점을 받았다.
그래서 찾아보니 '에라토스테네스의 체'라는 알고리즘이 있어 공부했고, 이를 토대로 코드를 작성해 제출했다.
초반 코드
사실 이 코드에서 sqrt값에 i+1이 아닌 i를 넣어주면 제대로된 값이 나오지않는데, 그 이유를 잘 모르겠다.
그래서 추후 다시 코드를 봐야 할 것 같다.
function solution(n){
var answer = 0;
let flag = 0;
for(let i=n; i>1; i--){
for(let j=2; j<Math.sqrt(i+1); j++){
if(i%j == 0){
flag = 1;
break;
}
}
if(flag == 0)
answer++
flag = 0;
}
return answer;
}
console.log(solution(5))
개선된 코드
let PrimeArray = [];
function Eratos(n){
if(n<=1) return;
for(let i=2; i<=n; i++){
PrimeArray[i] = true
}
for(let i=2; i*i <=n; i++){
if(PrimeArray[i])
for(let j=i*i; j<=n; j+=i)
PrimeArray[j] = false;
}
}
function solution(n) {
var answer = 0;
Eratos(n)
for(let i=2; i<=n+1; i++){
if(PrimeArray[i] == true){
answer++
}
}
return answer;
}
코드 개선 후 테스트 결과가 무척 좋아진 것을 확인할 수 있다.
위키백과에 있는 코드를 거의 그대로 사용했기 때문에 좀 더 완벽한 이해가 필요할 듯 싶다.
Author And Source
이 문제에 관하여([프로그래머스] 소수 찾기 - JS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yeseul/프로그래머스-소수-찾기-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)