[프로그래머스 코딩테스트 JavaScript] Level 1-33 소수 찾기

 

 

[프로그래머스 코딩테스트 JavaScript] Level 1-33 소수 찾기

 

 

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

nresult

10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

 

 

나의 코드 (실패1)

시간초과, 효율성 테스트 실패 

이중 for문이라 그런듯

 

 

 

실패 2  -> 7,11,13...등 무한한 소수의 배수는 처리를 못함. 

function solution(n){
    let a = []; 
    return hello(n)
    
    function hello (n){
        if(n%2==0){
            if(n==2){
                a.push(n);
                return a.length;
            }
            n--;
            return hello(n)
        }else if(n%3==0){
            if(n==3){
                a.push(n);
                n--;
                return hello(n)
            }
            n--;
            return hello(n)
        }else if(n%5==0){
            if(n==5){
                a.push(n);
                n--;
                return hello(n)
            }
            n--;
            return hello(n)
        }else{
            a.push(n);
            n--;
            return hello(n)
        }
    }
}

console.log(solution(49))
console.log(Math.sqrt(10))

 

 

 

무한한 소수를 구하는 공식이 없다고 없다고하는데 일단 위키백과에서 제한된 수 이내에 있는 소수 구하는 공식을 찾음 

 

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전

 

요 두번째 방법으로 다시 만들기 

 

 

실패 3 시간초과 

 

 

 

 

 

 

 

 

Math.sqrt로 

두번째 for문을 반으로 줄여도

filter가 들어가서 그런듯

그래도 첫번째 실패보다

정확성은 6-> 56으로 올랐다 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

실패 4 

 

 

 

 

 

 

 

 

 

 

 

 

눈물 난다 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

실패 5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

테스트는 이제 다 통과했는데

효ㅇ율성 시간초과 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

실패 6

 

 

 

 

 

 

 

 

 

 

 

 

재귀함수 시간 초과 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

실패 7

 

 

 

 

 

 

 

 

 

 

 

push, pop을 줄여도 안됨

효율성은 대체 뭐냐규ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

에라토스테네스의 체까지 알게됨

 

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

도 ~ 저히 내 머리로는 모르겠어서 찾아보니 요 에라토스테네스 체를 써야 풀 수 있다고 한다. 

쉬엇다해야겟다