소수 판별 알고리즘

단일 숫자 소수 판별

주어진 자연수 n에 대하여 소수의 여부를 확인하고 싶을 때는 n의 제곱근까지만 약수 여부를 검증하는 것이 가장 빠르다.

func isPrimeNumber(_ n: Int) -> Bool {
    let squareRoot = Int(sqrt(Double(n)))
    
    if n == 1 {
        return false
    }
    
    if n == 2 || n == 3 {
        return true
    }
    
    for number in 2...squareRoot {
        if n % number == 0 {
            return false
        }
    }
    
    return true
}

---

Sieve of Eratosthenes(에라스토테네스의 체)

2부터 n까지의 모든 소수를 찾는 방법이다.
원리: 범위만큼 배열을 생성하고, 소수가 아닌 수를 하나씩 지워나간다.
1. 각각의 값이 소수 여부를 나타내는 크기가 n+1인 Boolean 배열을 생성한다.
2. 2부터 시작해서 각 숫자의 배수들을 모두 false로 바꾼다.
3. 위의 과정을 끝까지 거친 후 true로 남아있는 수들이 n까지의 모든 소수이다.

func sieve(_ n: Int) -> [Int] {
    // 소수 판별 배열 생성
    var sieves = Array(repeating: true, count: n+1)
    sieves[0] = false
    sieves[1] = false
    
    // 2부터 n의 제곱근까지 탐색 시작
    // index의 배수 위치에 있는 모든 값을 false로 바꾼다.
    var index = 2
    while index * index <= n {
        if sieves[index] {
            var k = index * index
            while k <= n {
                sieves[k] = false
                k += index
            }
        }
        index += 1
    }
    
    // 소수인 숫자들만 따로 모은 배열 생성하여 리턴
    var primeNumbers = [Int]()
    for index in 0..<sieves.count {
        if sieves[index] {
            primeNumbers.append(index)
        }
    }
    
    return primeNumbers
}

이 알고리즘의 시간 복잡도는 O(nloglogn)이다.

---

Factorization(인수분해)

숫자를 주요 인수로 분해하는 과정을 인수분해라고 한다. 주어진 숫자 n에 대하여 n을 소수끼리의 곱으로 인수분해하려고 한다.
위의 아리스토테네스의 체 알고리즘을 약간 수정하여 빠른 인수분해가 가능하다.

먼저 인수분해를 하기 위한 배열 생성이 필요하다.

func prepareArrayForFactorization(_ n: Int) -> [Int] {
    var array = Array(repeating: 0, count: n+1)
    var index = 2
    
    while index * index <= n {
        if array[index] == 0 {
            var k = index * index
            while k <= n {
                if array[k] == 0 {
                    array[k] = index
                }
                k += index
            }
        }
        index += 1
    }
    return array
}

이 함수는 소수인 경우 0, 소수가 아닌 수는 자신을 구성하는 가장 작은 소수로 구성된다. 예를 들어 만약 n = 20이라면 다음과 같이 배열이 생성된다.

다음으로 주어진 수 n에 대하여 소인수 분해를 하는 함수를 작성한다.
위에서 만든 배열의 값으로 n을 계속 나누어 0이 나올 때까지 나눈 수를 primeFactors 배열에 담고, 마지막으로 나누고 남은 수까지 넣어주면 소인수분해가 완료된다. 예를 들어 n = 20이라면 소인수분해의 결과로 [2, 2, 5]를 반환하게 된다.

func factorization(_ n: Int) -> [Int] {
    var primeFactors: [Int] = []
    let array = prepareArrayForFactorization(n)
    
    var x = n
    
    while array[x] > 0 {
        primeFactors.append(array[x])
        x /= array[x]
    }
    primeFactors.append(x)
    return primeFactors
}

이 함수의 시간 복잡도는 O(log x)이다.