[JavaScript] 소수 찾기 - Level 1

 

코드

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

1. 소수 개수를 의미하는 변수 result, 1부터 n까지 나누어 떨어지는 숫자의 개수를 의미하는 변수 count 선언
2. 0과 1을 제외한(소수이기 때문) 2부터 n까지 반복문을 돌며 1부터 n까지 나누어 떨어지는 숫자의 개수를 count 한다.
3. count 개수가 2인(1과 자기 자신으로만 나누어 떨어지는 = 소수) 숫자를 찾으면 result 에 +1을 해준다.
4. result를 return 하여 소수 개수를 구한다.

 

결과

• 이중 for문을 사용해 2부터 n까지 돌며 소수인지 체크하고, 소수라면 result를 증가시켰더니 나온 결과이다.

 

왜 시간 초과가 나오게 되었을까?

• i가 n에 가까워질수록 내부 for문도 n회에 가깝게 반복하게 되므로 시간 복잡도는 O(N^2)가 된다...

• O(N^2)의 시간복잡도를 가지게 되면 input의 값이 커질수록 시간은 기하급수적으로 올라간다.

 

소수 찾기 : 에라토스테네스의 체

• 시간 초과 이슈를 해결하기 위해서는 에라토스테네스의 체에 대해 알아야 한다.

• 위의 그림과 같이 N을 120이라 가정하고, 소수가 아닌것을 체크한다.
  1. 2는 소수이다.
  2. 2를 제외한 2의 배수들은 2를 약수로 가지고 있으나 소수가 아니다.
  3. 3은 소수이다.
  4. 3을 제외한 3의 배수들은 소수가 아니다.
  5. 4는 소수가 아니므로 넘어간다.
  6. 5는 소수이다. 
  
  
• 이런 방식으로 120까지 반복하면 체크되지 않은 소수들만 남게 된다.

 

코드

function solution(n) {
    const arr = []

    for (let i = 0; i < n + 1; i += 1) {
        arr.push(true)
    }
    
    for (let i = 2; i * i <= n; i += 1) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false
            }
        }
    }
    
    arr.splice(0, 2, false, false)
    
    return arr.filter(v=> v).length
}

1. 인덱스 번호가 주어진 숫자 n과 대응하도록 빈 배열을 만들고 원소는 true 값으로 채워준다.
2. (true는 소수라는 의미이다.)
3. 배열은 0부터 시작하므로 0부터 n+1까지 반복문을 돌린다.
4. 주어진 수의 제곱근까지만 계산해서 반복을 최소화한다.
5. arr[i]가 소수일 경우, 반복문을 진행한다.
6. 맨 처음 시작하는 2는 소수이므로, 2를 제외한 2의 제곱부터, 제곱 값만 체크하여 지워나간다.
7. 제곱근까지 반복한다.
8. 0과 1은 소수가 아니므로 false 값으로 바꿔준다.
9. 배열에서 true 인 값의 개수를 출력한다.

 

다른 사람의 풀이

// 내가 짠 코드

for (let i = 0; i < n + 1; i += 1) {
        arr.push(true)
    }

arr.splice(0, 2, false, false)

// 더 간단한 방법

let arr = Array(n+1).fill(true).fill(false, 0, 2)

나는 반복문을 돌면서 true 값을 push 한 후 0과 1은 splice를 사용하여 false로 바꿔줬는데,

fill을 사용하여 배열을 같은 값으로 채운 후 0과 1을 false로 바꿔주는게 더 간단한 것 같다!