[알고리즘스터디 with 케이시] 소수구하기

정의

• 소수(prime)
  • 1과 자기 자신만을 약수로 가지는 수를 의미한다.
• 소수를 구하는 효율적인 방법을 알아보자.

어떤 숫자 N 이 소수인지 판별하는 방법

1. 가장 직관적인 방법

• 2부터 N -1 까지 루프를 돌면서 나눠보기
• 시간복잡도O(n)
• 코테에 부적합

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

2. 효율성을 개선한 방법

• 그 어떤 소수도 N 의 제곱근 보다 큰 수로 나눠지지 않는다는 점을 이용
  • 여기서 N 이 “그 어떤 소수” 이다.
  • 시간 복잡도 O(sqrt(n))
• 예시 - 17
  • 17의 제곱근은 4.xx
  • 2, 3, 4 로만 나눠봐서 소수인지 확인 하면 된다.
  • 왜 와이?
  • 5 이상의 수는 제곱을 하면 17을 넘어간다(25)
  • 다시 말하면, 5이상의 수로 나눠지면 소수가 아니다
    • 예) 20, 2,4,5, 5로 나눠짐. 소수 x ****

코드

func isPrime(number: Int) -> Bool {
    for i in 2..<number {
        if i * i > number {
            break
        }
        if number % i == 0 {
            return false
        }
    }
    return true
}

여러 숫자를 소수인지 아닌지 판별하는 에라토스테네스의 체

2 부터 N 까지의 수 중 소수를 골라내는 로직이다.

방식은 간단하다.

• 2
  • 1과 자기 자신으로 나눠지므로 소수
  • 2의 배수는 다 컷(4,6,8,…54)
• 3
  • 1과 자기 자신으로 나눠지므로 소수
  • 3의 배수는 다 컷(6,9,12,15,18,21…51)
• 4
  • 2의 배수이므로 넘어감
• 5
  • 1과 자기 자신으로 나눠지므로 소수
  • 5의 배수 컷 ..
• 7
  • 1과 자기 자신으로 나눠지므로 소수
  • 7의 배수 컷

자 여기서부터가 중요하다.

위와 같은 단계를 거친 모습인데, 여기서 아직 색칠해지지 않은 수는 소수라고 할 수있다.

왜 와이?

• 그 어떤 소수도 N 의 제곱근 보다 큰 수로 나눠지지 않는다

즉, 54의 제곱근인 7.xx 보다 큰 8 이상의 수는 확인할 필요가 없이 소수인 것이다.

• 예를들어 29를 보자.
• 이 수의 제곱근은 반드시 7.xx 보다 작다
• 이 수의 제곱근은 5.xx다
• 5까지는 이미 다 체크했다.
• 이 수가 소수다.

체크되지 않은 모든 수가 소수다.

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

코드

func getPrimes(number: Int) -> [Int] {
    var prime = [false, false]
    let initPrime = Array<Bool>(repeating: true, count: number - 1)
    initPrime.forEach { prime.append($0) }      

    for i in 2..<number {
        if i * i > number {
            break
        }
        if prime[i] {
            for j in stride(from: i*2, through: number, by: i) {
                prime[j] = false
            }
        }
    }

    return prime.enumerated().compactMap {
        if $0.element == true {
            return $0.offset
        }
        return nil
    }
}

출처

케이시 강의