[230422] 소수 찾기

 

 

문제

프로그래머스

 

 

 

풀이

첫 번째 풀이

function solution(n) {
    let answer = 1;
    for(let i = 3; i <= n; i++){
        let flag = true;
        for(let j = 2; j < i; j++) {
            if(i % j === 0) flag = false;
        }
        if(flag) answer++;
    }
    return answer;
}

간단하게 생각하고 풀었다.

n은 2 이상이니까 무조건 2는 포함한다 생각하고 answer = 1로 두고, i는 3부터 시작하도록 했다.

flag를 세워서 2~i까지 수 중에서 나눠지는게 있으면 false로 두도록했다.

하나라도 false라도 for문을 끝까지 다 도는게 맘에 걸리긴 했지만 일단 돌려봤다.

 

결과는… 효율성 똥망

테케 10, 11, 12 실패, 효율성 테스트 올실패 (그럴 수 밖에)

 

 

 

두 번째 풀이

근데 생각해보니까 모든 숫자를 다 돌릴 필요가 없다고 생각했다.

빈 배열에 소수가 등장할 때마다 소수를 집어넣고,

값을 배열에 있는 소수로 나눴을 때 안나뉘면 그 값이 또 소수 아닌가?

그리고 마지막엔 배열의 길이를 리턴하면 됨.

…

라는 아이디어로 일단 코드를 다시 짜봤음.

function solution(n) {
    const arr = [2];
    
    for(let i = 3; i <= n; i++) {
        let flag = true;
        for(let j = 0; j < arr.length; j++){ 
            if(i % arr[j] === 0) {
                flag = false;
                break;
            }
        }
        if(flag) arr.push(i)
    } 
    return arr.length;
}

정확성은 올통과인데 효율성은 아직도 시간 초과다.

 

 

세 번째 풀이

질문하기의 힘을 빌렸다..

Math.sqrt(n)보다 작은 소수들로 나눠 떨어지지 않으면 n은 소수라 한다.

그래서 for문의 범위를 변경했다.

function solution(n) { 
    console.log(Math.sqrt(4))
    const arr = [2];
    
    for(let i = 3; i <= n; i+=2) {
        let flag = true;
        for(let j = 0; j < Math.sqrt(i); j++){ 
            if(i % arr[j] === 0) {
                flag = false;
                break;
            }
        }
        if(flag) arr.push(i)
    } 
    return arr.length;
}

그랬더니 바로 통과했다.

 

 

---

얻은 Tips

1. 1부터 연속된 수 담기

[...Array(n).keys()]

2.

Math.sqrt(n) === n**.5