[JavaScript] 소수찾기

[ah-ryeong]

문제

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

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

제한 조건 n은 2이상 1000000이하의 자연수입니다.

• 너무 못 풀어서 '에라토스테네스의 체' 힌트받고 봤는데 이해 안 돼서 진짜 하나씩 i값 j값 arr값 찍어보면서 이해하는데 하루 걸림
• 웬만하면 코드펜에서 돌려보고 정리해서 git에 풀이 업로드 하는데 이건 꼭 찍어본 바보짓도 업로드 해야할 것 같다.

function solution(n) {
    var answer = 0;
    let arr = [];

    for(let i = 2; i <=n; i++) {
        arr[i] = i
    }

    // arr = [, , 2, 3, 4, 5, 6, 7, 8, 9, 10];

    for(let i =2; i <= n; i++) {
        console.log(`i ::: ${i} `); // 2 3 4 5 6 7 8 9 10 
        for(let j = i+i; j <=n; j+= i ) {
            console.log(`j ::: ${j} `); // 4 6 8 10 / 6 9 8 10
            if(arr[j] === 0) { continue; }
            arr[j] = 0
        }
    }

    console.log(arr);
    answer = arr.filter((item) => item !== 0).length;
    return answer;
}

solution(10);

이 코드 효율성에서 통과 안됨..🤦‍♀️

[ah-ryeong]

어? 콘솔로그 지우고 어쩌고 저쩌고 하니까 효율성 테스트에서 통과했다. ^^; 나는 바보다. 원래 다른 사람 풀이 늘 체크하고 보는데 이거는 다른 사람 풀이를 봐도 이해 못 할 것 같다. ^^>

이상하다 위에 코드처럼 콘솔로그 남발 안 하고 마지막에 딱 하나 썼는데 이게 효율성에서 걸려버리나..?

이유는 제한조건이 1000000이하의 자연수니까, 콘솔로 배열을 찍어버리니 백만개까지 콘솔로 배열을 찍어내면서 테스트하면 효율성이... 아무튼 이게 원인이었다.

[ah-ryeong]

전

function solution(n) {
    let arr = [];

    for(let i = 2; i <=n; i++) {
        arr[i] = i
    }

    for(let i =2; i <= n; i++) {
        for(let j = i+i; j <=n; j+= i ) {
            if(arr[j] === 0) { continue; }
            arr[j] = 0
        }
    }

    console.log(arr);
    return arr.filter((item) => item !== 0).length;

}

[ah-ryeong]

후

function solution(n) {
    let arr = [];
    for(let i = 2; i <=n; i++) {
        arr[i] = i
    }
    for(let i =2; i <= n; i++) {
        for(let j = i+i; j <=n; j+= i ) {
            if(arr[j] === 0) { continue; }
            arr[j] = 0
        }
    }
    return arr.filter((item) => item !== 0).length;
}