소수 찾기 메모

function solution(n) {
    var answer = 0;
    let count = 0;
    let arr = new Array();
    //소수가 아닌 것들을 빼면 소수가 됨
    //자기자신을 제외한 모든 배수를 n개의 숫자 내에서 확인
    //확인된 숫자를 다 0으로 두면 나머지가 소수
    //n 까지 숫자를 전부 배열에 일단 넣고 확인하자
    for (let i = 2; i <= n; i++) {
        arr[i] = i;
    }
    //소수는 임의숫자 x의 배수가 아니어야 함, 자기자신과 1만 배수임
    //제곱근까지만 나누어서 나머지가 없으면 소수가 아님(루트 9면 3)
    //나눠서 나머지 없는 애들을 0으로 설정하자
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (arr[i] == 0) { // 이미 체크된 수의 배수는 확인하지 않는다
            continue;
        }
        
        for (let j = i + i; j <= n; j += i) { // i를 제외한 i의 배수들은 0으로 체크, 소수가 아닌 애들
            arr[j] = 0;
        }
    }
    
    for (let i = 2; i <= n; i++) {
        if(arr[i] != 0){
             count++;
        }
    }
    return count;
}

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

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

제한 조건

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

해당 문제에 대해 풀었던 방법. 프로그램상에서 소수를 체크하는 법에 대한 새로운 아이디어를 기억해두고자 메모함

소수는 자신과 1만을 약수로 갖는 수, 반대로 말하자면, 최소수와 n수 사이에 자신과 1 외에 다른 나눠지는 배수가 있다면 소수가 아니라는 것.

n까지의 각 숫자를 체크하기 위해 배열에 넣고 i번째 배열에 n수까지의 i번째 수를 순서대로 넣는다.

해당 배열을 반복문을 돌리면서, 2부터 (1을 제외한 제일 낮은 소수) 숫자를 하나씩 올리면서 n 안에서 i + i(i의 배수)

인 해당 배열이 있는지를 확인한다. n 안에 그 길이까지 배열이 있다면 해당 배수가 있으니 소수가 아닌것. 이런 원소를 0으로 만들어준다.

그 뒤에 다시 i를 하나 올리고 반복해서 2의 배수 3의배수 4의 배수 5의 배수 이런식으로 배수를 지우되

이미 0이된건 continue를 이용해서 바로바로 넘어간다

이러다보면 뒤로갈수록 빨라짐(0이 늘어나니까)

이렇게 배열을 바꿔두면 배열엔 소수만남음

그럼 소수알고싶으면 해당 배열에서 0 제외한걸 확인하면 됨