[Codility] 10. Prime and composite number

10.1 Counting divisors (제수 세기)

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

$n=36$

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}$

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$