Swift

에라토스테네스의 체와 Stride()

leeyuno 2021. 1. 15. 17:47

알고리즘 문제를 풀다 소수찾기가 필요한 문제를 접했다.

특정 범위가 주어지는 문제이기 때문에 시간효율 제약이 있었고 기존 소수찾기로는 타임아웃이 되어버렸다.

에라토스테네스의 체를 이용하여 풀어야 했다.

 

에라토스테네스의 체란 특정 범위 안의 소수를 찾는 가장 빠른 방법이다.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

이렇게 숫자가 주어지면

 

먼저 1은 소수가 아니라 지워버린다

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

 

그리고 2를 제외한 2의 배수를 지운다

  2 3   5   7   9  
11   13   15   17   19  
21   23   25   27   29  
31   33   35   37   39  
41   43   45   47   49  
51   53   55   57   59  
61   63   65   67   69  
71   73   75   77   79  
81   83   85   87   89  
91   93   95   97   99  

 

그 다음 2을 제외한 3의 배수를 지운다

  2 3   5   7      
11   13       17   19  
    23   25       29  
31       35   37      
41   43       47   49  
    53   55       59  
61       65   67      
71   73       77   79  
    83   85       89  
91       95   97      

 

그 다음 5, 7 도 같은 방법으로 지우게 되면

 

  2 3   5   7      
11   13       17   19  
    23           29  
31           37      
41   43       47      
    53           59  
61           67      
71   73       77   79  
    83           89  
            97      

 

이렇게 소수가 남는다. 이렇게 에라토스테네스의 체를 사용하면 배수를 모두 지워야 해서 아주 큰 범위에서는 비효율적이지만

문제에서 1 ~ 100까지 처럼 범위가 작으면 아주 빠르게 계산이 가능하다.

 

이렇게 계산을 해줄때 stide 함수를 사용하면 좀 더 간편하게 계산이 가능하다.

 

func stride<T>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T> where T : Strideable

 

start: 시작 값, end: 끝 값 (end는 시퀀스에 포함되지 않음), stride: 얼만큼의 보폭으로 진행할지 를 나타냅니다.

 

먼저 예제 1번을 보면 

0.0부터,  pi * 2 까지, pi / 2씩만큼 증가

for radians in stride(from: 0.0, to: .pi * 2, by: .pi / 2) {
    let degrees = Int(radians * 180 / .pi)
    print("Degrees: \(degrees), radians: \(radians)")
}
// Degrees: 0, radians: 0.0
// Degrees: 90, radians: 1.5707963267949
// Degrees: 180, radians: 3.14159265358979
// Degrees: 270, radians: 4.71238898038469

 

3부터 0까지 -1씩 증가

for countdown in stride(from: 3, to: 0, by: -1) {
    print("\(countdown)...")
}
// 3...
// 2...
// 1...

 

0부터 10까지 -1씩 증가

for x in stride(from: 0, to: 10, by: -1) {
    print(x)
}
// Nothing is printed.

 

through를 이용하면 end범위까지 포함해서 사용할 수 있다.

func stride<T>(from start: T, through end: T, by stride: T.Stride) -> StrideThrough<T> where T : Strideable

 

소수 찾기 문제에 적용한 예를 보면

1부터 입력받은 n까지 소수인지 아닌지 여부를 담은 배열을 하나 만들고

for문을 통해 2 ~ n까지 반복 (1은 소수가 아니기 때문에)

순서대로 2, 3, 5, 7을 만나기때문에 i를 1씩 증가시키면서 for문을 돌린다.

 

그리고 stride를 사용해서 i번째를 만나게 되면 stride를 이용해 i의 배수를 모두 지워버린다.

예를들어 처음 2를 만나게 되면

stride함수를 통해 2부터 n + 1까지 2씩 증가시키면서 배열안의 소수를 검증한다.

다음 3을만나면 3부터 n + 1까지 3씩 증가시키면서 배열안의 소수를 검증한다.

 

이런식으로 소수찾기에 stride함수를 사용할 수 있다.

 

func solution(_ n:Int) -> Int {
    var result = 0

    var array = Array(repeating: false, count: n + 1)

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

    return result
}