[Codility] 10. Prime and composite number

10.1 Counting divisors (제수 세기)

어떤 수 $n$의 divisor를 구해보자. brute-force한 방법으로 1부터 $n$까지 반복문을 돌릴 수 있다. 이때 시간복잡도는 $O(n)$이 된다.

$n=36$인 경우를 생각해보자. $2 \times 8 = 16$이므로 $17$~$35$의 수는 체크할 필요가 없다. 또 $6 \times 6 = 36$이므로 $7$~$35$의 수는 체크할 필요가 없다. 따라서 $\sqrt{n}$까지만 조사하면 된다.

def divisors(n):
    i = 1
    result = 0 # n의 divisor의 개수
    while i * i < n:
        if n % i == 0:
            result += 2
        i += 1
    
    # n이 제곱수일 때
    if i * i == n:
        result += 1
   return result

10.2 Primarility test (소수 판정)

10.1에서 설명한 divisor를 살짝 이용하면 쉽게 판정할 수 있다. 시간복잡도는 역시 $O(\sqrt{n})$이다

def primality(n):
    # n이 소수라면 True, 아니라면 False를 반환
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

10.3 동전 뒤집기

1. n개의 동전이 있다. 각 동전은 처음에 모두 윗면(head)을 향해있다
2. n명의 사람이 순서대로 동전을 뒤집는다.
3. i번째 사람은, i의 배수에 있는 동전을 뒤집는다. 윗면(H)이라면 아랫면(tail)로, 아랫면이라면 윗면으로 뒤집는다.
4. 모든 사람이 동전을 다 뒤집었을 때, 윗면(head)를 향하는 동전의 개수는?
5. 그림은 10개의 동전일때 결과이다. 앞면을 향하는 동전은 7개이다.

10.3.1 $O(n\log{n})$ - 시뮬레이션

각 사람들의 순서마다 직접 동전을 뒤집는다. 첫번째 사람은 $n$개, 두번째 사람은 $n \over{2}$개, 세번째 사람은 $n \over{3}$개, ....$n$번째 사람은 1개의 동전을 뒤집는다. 따라서 시간복잡도는 반복횟수는 $n(1 + \dfrac{1}{2} + \dfrac{1}{3} + ... +\dfrac{1}{n}) \approx n \log{n}$이므로 시간복잡도는 $O(n\log{n})$이다.

10.3.2 $O(\sqrt{n})$ - 뒤집어지는 횟수 관찰

사실 이 시행을 잘 관찰하면, $i$번째 동전은 $i$의 divisor의 개수만큼만 뒤집어진다. 예를 들면, 3번째 동전은 1, 3일때만, 10번째 동전은 1, 2, 5, 10인 경우에만 뒤집어진다.
그리고 divisor의 개수는 대칭적이어서 10.1에서 보았듯이 제곱수의 경우에만 그 개수가 홀수개이고, 나머지는 짝수개이다.
따라서 1부터 $n$까지 중에서 제곱수인 것들만 동전이 뒤집어지고 나머지는 그대로가 된다.
반복횟수는 $\lfloor \sqrt{n} \rfloor$만큼만 조사하면 된다. $O(\lfloor \sqrt{n} \rfloor) \approx O(\log{n})$이라고 알려져있다. (이유는 모르겠다..... $\sqrt{n}$이랑 $\log{n}$이랑 시간복잡도가 다르지 않나...?)