소수 구하기

안녕하세요. KataRN입니다.

 

코테 문제를 풀다보면 소수를 구하는 문제가 많습니다.

보통 소수관련 문제가 나오면 효율성도 좋아야 되더라구요... 그리고 소수와 효율성하면 꼭 언급하는 이론이 있습니다.

 

그건 바로 '에라토스테네스의 체' 입니다.

소수를 하나하나 구하는것보다 아래의 그림처럼 소수의 배수를 제거하는것이 빠릅니다.

출처:위키백과

 

이를 포함하여 소수판별코드, 소수의개수, 소수구하기 등을 코드로 구현해봤습니다.

 

소수 판별 코드(swift)

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

 

1부터 n까지 소수 배열 구하기 - 에라토스테네스의 체

func primeArr(_ n:Int) -> [Int] {
    var arr = Array(repeating: false, count: n + 1)
    var answer = [Int]()
    for i in 2...n{
        if arr[i] == false{
            answer.append(i)
            for j in stride(from: i, to: n + 1, by: i){
                arr[j] = true
            }
        }
    }
    return answer
}

<응용코드>

1부터 n까지 소수 개수 구하기 - 에라토스테네스의 체

func primeCount(_ n:Int) -> Int {
    var count = 0
    var arr = Array(repeating: false, count: n + 1)

    for i in 2...n{
        if arr[i] == false{
            count += 1
            for j in stride(from: i, to: n + 1, by: i){
                arr[j] = true
            }
        }
    }
    return count
}

 

이처럼 좋은 기본코드 하나만 제대로 알고있으면 다양하게 활용할 수 있습니다.

오늘도 읽어주셔서 감사합니다.