10. 소수와 합성수 (Prime and Composite Numbers) Codility Lesson 한국어 정리본 (JavaScript ver.)

소수(Prime Number)와 합성수(Composite Number)

소수(Prime Number) 는 1보다 크고, 자기 자신과 1을 제외한 약수가 없는 수 를 의미한다.

합성수(Composite Number) 는 1과 자기 자신 이외에도 다른 약수를 가지는 수 를 의미한다.

예를 들어, 2, 3, 5, 7, 11, 13 등은 소수이며, 4, 6, 8, 9, 10 등은 합성수이다.

---

1. O(√n) 시간 복잡도의 약수 개수 구하기

n의 약수를 찾는 기본적인 방법은 1부터 n까지 모든 수를 확인하는 것 이다. 하지만 n의 약수는 대칭성을 가지므로, √n 까지만 탐색해도 전체 약수를 구할 수 있다.

JavaScript 코드:

function countDivisors(n) {
    let count = 0;
    let i = 1;
    
    while (i * i < n) {
        if (n % i === 0) {
            count += 2; // i와 n/i 두 개의 약수 추가
        }
        i++;
    }
    
    if (i * i === n) {
        count += 1; // 제곱수일 경우 중복 제거
    }
    return count;
}

시간 복잡도: O(√n)

---

2. O(√n) 시간 복잡도의 소수 판별

소수인지 확인하는 방법:

• 2부터 n-1까지 모든 숫자로 나누어 보면 O(n) 시간이 걸림.
• √n까지만 검사하면 O(√n)으로 최적화 가능

JavaScript 코드:

function isPrime(n) {
    if (n < 2) return false;
    let i = 2;
    while (i * i <= n) {
        if (n % i === 0) return false;
        i++;
    }
    return true;
}

시간 복잡도: O(√n)

---

3. 동전 뒤집기 문제 (Coin Flipping Problem)

n개의 동전이 일렬로 놓여 있고, 초기에는 모두 앞면(Heads)이다.

• i번째 사람이 배수 위치의 동전을 뒤집는다. (예: i = 3이면 3, 6, 9, ...을 뒤집음)
• 최종적으로 뒷면(Tails)이 보이는 동전의 개수를 구하는 문제.

O(n log n) 해결법 (시뮬레이션)

function countTails(n) {
    let result = 0;
    let coin = new Array(n + 1).fill(0);
    
    for (let i = 1; i <= n; i++) {
        let k = i;
        while (k <= n) {
            coin[k] = (coin[k] + 1) % 2;
            k += i;
        }
        result += coin[i];
    }
    return result;
}

시간 복잡도: O(n log n)

---

O(√n) 해결법 (수학적 최적화)

뒤집힌 횟수가 홀수인 동전 만 뒷면을 보이게 된다. 이는 약수의 개수가 홀수인 경우인데, 제곱수만 홀수 개의 약수를 가진다. 즉, 1, 4, 9, 16, ...의 개수를 찾으면 된다.

function countTailsOptimized(n) {
    return Math.floor(Math.sqrt(n));
}

시간 복잡도: O(1) (제곱근 계산)