@소수 찾기

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

시도

function solution(n) {
    var answer = 0;
    for(let i =1;i<=n;i++){
        let count = 0
        for(let j=1;j<=i;j++){
            if (i%j==0) count++
        }
        if (count == 2) answer++
    }
    return answer;
}

먼저 생각나는대로 for 문을 두개 돌려봤는데 역시나 시간 초과로 실패가 떴다

그러면 count 가 3이 된 순간 break 하면 좀 낫지 않을까?

데이터의 양은 많이 줄어들었지면 여전히 시간 초과다

for 문을 중첩하여 사용하는 것 자체를 하면 안될 것 같은 느낌이다
아니면 2 나 3으로 나누어 떨어지는 값을 빼고 for 문을 돌리면 어떨까?

function solution(n) {
    var answer = 0;
    for(let i =1;i<=n;i++){
        let count = 0
        if (i > 2 && i%2==0) continue
        if (i > 3 && i%3==0) continue
        for(let j=1;j<=i;j++){
            if (i%j==0) count++
            if (count == 3) break
        }
        if (count == 2) answer++
    }
    return answer;
}

if 문을 두개 더 거쳐야 하기 때문에 오히려 데이터가 늘었다

function solution(n) {
    var answer = 0;
    if (n>3) answer = answer +2
    else if (n==2 ) return 1
    else if (n==3) return 2
    for(let i =3;i<=n;i +=2){
        let count = 0
        for(let j=3;j<=i;j+=2){
            if (i%j==0) count++
            if (count == 3) break
        }
        if (count == 1) answer++
    }
    return answer-1;
}

2,3 을 제외해주고 홀수만 가지고 계산하는 방법으로 해도 시간초과

중첩 for 문을 아예 사용하면 안되는 듯 하다

에라토스테네스의 체

에라토스테네스의 체 라는 소수를 찾는 방법이 있었다

n보다 작은 소수들의 집합은
2에서부터 루트n까지 각 수의 배수를 빼고 남은 수들의 집합과 같다
라는 방법이다

그 방법에 따라 코드를 작성해보았는

function solution(n) {
    let arr = []
    let answer = []
    for(let i = 2;i<n+1;i++){
        arr.push(i)
    }
    for(let j = 2;j<Math.sqrt(n);j++) {
        answer.push(arr[0])
        arr = arr.filter(val=>val%arr[0]!==0)
    }
    return arr.length+answer.length
}

아까보다 데이터는 현저히 줄었지만 효율성 테스트에서 떨어졌다

하지만 긴 배열을 사용하는 것 자체에서 이미 데이터를 많이 사용하게 되는 것 같다

아예 배열을 사용하지 않고 하는 방법이 필요해 보인다

해결

그렇게 함수 primeNumCount 를 하나 만들어서 선언하고
2의 배수를 제외한 수로 for 문을 돌리는 방법으로 풀어냈다

function primeNumCount(num) {
    for (let i = 3; i<=Math.sqrt(num);i+=2){
        if (num%i == 0) return false
    }
    return true
}

function solution(n) {
    let count =1
    for(let i =3; i<=n; i+=2){
        if (primeNumCount(i)) count++
    }
    return count
}

결론

배열과 객체는 데이터의 크기가 매우 크다