[js] 합성수 찾기 (lv.0, 정답률 87%)

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 100

🫤 나의 풀이

function isPrime (num) {
    for (let i=2; i<=Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return num > 1;
}

function solution(n) {
    let compositeCount = 0;
    for (let i = 4; i <=n; i++) {
        if (!isPrime(i)) compositeCount++;
    }
    return compositeCount;
}

포문을 중첩해서 써야 하나... 하기 싫어하던 중에
'차라리 소수인 걸 확인하고 제외하는 게 낫지 않나?!'라는 생각이 들었다.

for문을 사용해서 2부터 num의 제곱근 숫자까지 반복한다. 어차피 제곱근을 넘어서는 약수는 볼 필요가 없기 때문이다. 그리고 num이 i로 나누어 떨어지면 소수가 아니기 때문에 false를 반환하고, num이 1보가 클 경우에만 true를 반환한다.

그리고 합성수를 구하는 방식은 그냥 4부터 (4미만은 어차피 합성수가 아님) n까지의 숫자가 소수가 아닐 경우만 compositeCount에 더해주면 되는 것이다.

오늘의 상식 - 합성수는 영어로 composite number

😊 다른 풀이 1

function solution(n) {
    let dp = new Array(n+1).fill(1)
    for(let i = 2 ; i <= n ; i++){
        if(dp[i]){
            for(let j = 2 ; i*j <= n ; j++){
                dp[i*j] = 0
            }
        }
    }

    return dp.filter(el => el === 0).length
}

dp는 크기가 n+1인 배열로 모든 요소가 1로 초기화되어 있다.
각 숫자가 소수인지 아닌지를 확인할 용도로 사용하는 것이다.

그 후 for문을 돌면서 i가 소수라면 i의 배수는 모두 소수가 아니라고 표시한다. 이것이... 에라토스테네스의 체 알고리즘의 핵심이라고 한다.

마지막으로 dp 배열에서 0의 개수를 세어서 개수를 반환하면 된다. (0이 바로 소수가 아닌 숫자)

♟️ 에라토스테네스의 체

소수를 찾는 가장 오래되고 유명한 알고리즘으로 소수의 배수들을 차례대로 제거해 가면서 소수만 남기는 것

1. 2부터 N까지의 모든 수를 나열합니다. (N은 찾고자 하는 최대 수입니다.)
2. 아직 지워지지 않은 수 중 가장 작은 수를 찾습니다. 이 수는 소수입니다.
3. 그 소수의 모든 배수를 목록에서 지웁니다. 단, 소수 자신은 지우지 않습니다.
4. 더 이상 수행할 수 없을 때까지 2단계와 3단계를 반복합니다.

[예시 코드]

function findPrimes(N) {
    let isPrime = Array(N + 1).fill(true); // 모든 수를 소수로 가정
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

    for (let i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= N; j += i) {
                isPrime[j] = false; // i의 배수들을 소수가 아닌 것으로 표시
            }
        }
    }

    // 소수 추출
    let primes = [];
    for (let i = 2; i <= N; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }

    return primes;
}

console.log(findPrimes(100)); // 100까지의 소수를 찾습니다.

이를 통해 N까지의 수 중에서 소수만을 효율적으로 걸러낼 수 있다.

😋 다른 풀이 2

function solution(n) {
  return Array(n)
    .fill()
    .map((_, i) => i + 1)
    .filter((i) => {
      let cnt = 0;
      for (let j = 1; j <= i; j++) {
        if (i % j === 0) cnt++;
      }
      return cnt >= 3;
    }).length;
}

Array(n).fill()을 통해서 길이가 n인 배열을 생성하고 전부 undefined로 초기화한다.

그리고 .map((_, i) => i+1)을 통해서 각 요소를 해당 요소의 인덱스 + 1로 매핑한다.

filter를 통해서 조건에 맞는 요소만 필터링한다. (조건 - 약수의 개수가 3개 이상인 수)

조건
내부에서 let cnt = 0을 선언하고, 1부터 i까지의 모든 수에 대해서 i를 나누어서 나머지가 0인 경우, 즉 약수인 경우 cnt를 1씩 증가시킨다.
최종적으로 cnt가 3 이상인 경우만 필터링하여

필터링된 요소의 길이를 반환한다.