✔️합성수 찾기

문제설명

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

제한사항

• 1 ≤ n ≤ 100

답

내가 쓴 답

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

※ 참고로 틀린 답이다. 어디가 틀렸을까?
처음에 문제를 잘못 이해해서 자연수 n이하의 모든 합성 수라는 조건을 고려하지 않아서 이상한 코드를 작성해 버렸다.

2차 풀이

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

한 함수안에 같은자리에다 return을 2번함
→ 스코프에 대한 개념이 부족한 것으로 보인다. 참고로 if문과 loop는 스코프의 유형이 다른 스코프와 다르다.

수정한 답

function solution(n) {
    let count = 0;
    for (let i = 4; i <= n; i++) { 
        let divisors = 0;
        for (let j = 1; j <= i; j++) {
            if (i % j === 0) {
                divisors++;
            }
        }
        if (divisors >= 3) {
            count++;
        }
    }
    return count;
}

여러종류의 풀이 보기

1번

function solution(n) {
    let count = 0;
    let tar = 3;
    while (tar++<n) {
        for (let i = 2; i <= Math.sqrt(tar); i++) {
            if (tar%i===0) {
                count++;
                break;
            }
        }
    }
    return count;
}

2번

function solution(n) {
    let count = 0;
    let tar = 3;
    while (tar++<n) {
        for (let i = 2; i <= Math.sqrt(tar); i++) {
            if (tar%i===0) {
                count++;
                break;
            }
        }
    }
    return count;
}

소수를 찾기위해 제곱근을 이용한다는 사실을 알 수 있었다.

왜 제곱근을 기준으로 하는가?

소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나게 됩니다. 따라서 소수인지 판별할때는 그 자연수의 제곱근 이하의 수까지만 검사를 하면 된다. 검사할 데이터를 제곱근 개 이하로 줄일 수 있다.

√24 를 기준으로 한다 할 때

2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2

https://velog.io/@tmpks5/Algorithm-소수를-판별하는-방법-제곱근-나누기

후기

보기엔 뭔가 쉬우면서 알듯말듯했지만 막상 풀어보면 깊이 생각을 해봐야했던 문제였다.

이중 for문을 돌려야겠다고 생각은 했지만 그냥 단순히 for문안의 for문을 적어야겠다고 생각했지만, 해보니 그게 아니었다. 조금 더 생각해봐야하는 문제였다.
평소에 풀던 for문과 if문이 섞인 문제보다 조금 더 난이도 있는 문제였던 것 같다.

그리고 조금 더 생각해보면 불필요한 행동들을 최소화할 수 있다는 것을 배울 수 있었다.