[Swift 알고리즘] 소수 판별

코딩 테스트 연습문제로 종종 나오는 소수 찾기에 대해 제대로 알아보자

 

소수 Prime Number 

: 1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 자연수

 

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,… 등은 모두 소수

소수가 아닌 자연수는 합성수

1은 소수도 합성수도 아니다. 

 

소수 판별법 1

자연수 n이 소수인지 아닌지를 판정하려면, 

인 범위에 있는 모든 소수 p로 n을 나누어 보아, 나누어 떨어지지 않으면 소수이고, 나누어 떨어지면 합성수이다. 즉, 소수는 양의 약수로 1과 자신만을 가진 자연수이며 합성수는 양의 약수가 1과 자기자신을 포함하여 3개 이상인 자연수이다.

참고 : 네이버 지식백과

 

어떤 자연수가 소수임을 판정하기 위해서는 √n 까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다. 

위 방법은 다음과 같이 코드로 표현할 수 있다. 

import Foundation

func isPrime(num: Int) -> Bool {
    if (num < 4) {
        return num == 1 ? false : true
    }
    for i in 2...Int(sqrt(Double(num))) {
        if (num % i == 0) { return false }
    }
    return true
}

참고 : keeplo tistory - isPrime 소수판별

 

제곱근을 반환해주는 sqrt 메소드는 Double 인자를 받아 Double을 반환하기 때문에

인자는 Double로, 결과값은 Int로 타입을 변환 해주어야 한다. 

func sqrt(_: Double) -> Double

 

소수 판별법 2 - 에라토스테네스의 체

Eratosthenes' sieve

: 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

2부터 n까지의 숫자중에서 에라토스테네스의 체로 소수를 찾으려면, 2부터 시작해 n까지의 자연수를 차례로 쓴다. (2, 3, 4, ..., n)
그리고 2 이외의 2의 배수를 지운다(p=2). 이때 2가 최초의 소수가 된다.
그 다음 소수인 3을 제외한 3의 배수를 지운다(p=3).
이 방법을 다음에 지울 소수, 즉 p의 제곱이 n 보다 커질 때까지, 이 방법을 계속한다(p2≥n).

그러면 체로 친 것처럼 끝에 남는 수가 있다. 이 수가 바로 그 자신과 1 이외의 다른 수로는 나누어 떨어지지 않는 소수이고, 이렇게 소수를 찾는 방법을 에라토스테네스의 체라고 한다. 이 과정은 끝없이 계속되지만 20까지 자연수를 지워나가도 소수가 2, 3, 5, 7, 11, 13, 17, 19임을 쉽게 알 수 있다.

메모리나 시간에 민감할 정도로 많은 수를 확인할 때에는 에라토스테네스의 체를 활용해 나올 수 있는 수의 최대 수까지 미리 판별하는 방법도 있다.

func sieveOfEratosthenes(num: Int) -> [Int] {
    var arr = Array(repeating: true, count: num+1)
    var primes = [Int]()
    for i in 2..<num {
        if arr[i] == true {
            for j in stride(from: i, through: num, by: i) {
                    arr[j] = false
            }
            primes.append(i)
        }
    }
    return primes
}

print(sieveOfEratosthenes(num: 1000)) //[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]