프로그래머스 - L1 소수 찾기

설계

소수를 판단하는 함수 구현

∙ 1…N/2 순회하여 나눠지는 값이 있는 경우 소수가 아니라 판단

반복문을 통해 숫자 하나씩 소수를 판단

∙ 소수인 경우 자신 제외 배수들은 소수가 아니기에 제외

∙ 소수가 아닌 경우 제외

계속 시간 초과로 인한 실패로 소수 찾기 알고리즘 확인

에라토스테네스의 체 알고리즘 확인 후 구현

소수 찾기 알고리즘 주제로 정리하여 포스팅하도록 하겠습니다!

;;; 처음 접하는 알고리즘이라 헤맸네요

git : 소수 찾기

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/132267

---

문제 풀이

에라토스테네스의 체 알고리즘을 간단하게 글로 설명드리면 !

1 부터 10 내 소수를 찾는다고 가정을 하면

∙ 1을 제외한 2 ~ 10을 쭉 나열합니다.

∙ 가장 작은 수를 뽑습니다. 해당 수는 소수이며, 자신을 제외한 범위 내 배수들을 제외시킵니다. 4, 6, 8. 10

∙ 제외한 수 반영하여 가장 작은 수를 뽑습니다. ( 3 ) 마찬가지로 자신을 제외한 배수들을 제외시킵니다. 6 , 9

∙ 이를 반복하면, 소수만 남게됩니다…

저는 배열의 index를 숫자라 생각하고 index에 해당하는 Bool 값으로 소수 판단을 진행하였습니다. index가 헷갈리지 않기 위해 길이 + 1의 배열을 생성했습니다.

에라토스테네스의 체 알고리즘은 2부터 시작하므로 0 과 1 은 제외시키기 위해 false를 수동적으로 넘어줍니다.

arrayOfNumber를 작은 수 부터 순회하면서 에라토스테네스 규칙대로 진행합니다.

import Foundation

func solution(_ n:Int) -> Int {
   
    var arrayOfNumber: [Bool] = Array.init(repeating: true, count: n + 1)
    arrayOfNumber[0] = false
    arrayOfNumber[1] = false
    
    arrayOfNumber.enumerated().forEach{ index, value in
        if(value) {
            var count = 2
            while(index * count < arrayOfNumber.count) {
                arrayOfNumber[index * count] = false
                count += 1
            }
        }
    }
    
    
    let result = arrayOfNumber.filter{ item in
        return item == true
    }
    
    return result.count
}

다른 사람 풀이 분석

프로그래머스 - Lee SeJin 님

func solution(_ n:Int) -> Int {
    var ch = Array(repeating: 0, count: n+1)
    var cnt = 0

    for i in 2...n {
        if ch[i] == 0 {
            cnt += 1
            for j in stride(from: i, to: n+1, by: i) {
                ch[j] = 1
            }
        }
    }

    return cnt
}

소수의 배수를 제외시킬 때 동일 간격의 반복 stride 활용

정리

∙ 대표적인 알고리즘은 숙지가 필요하다.

∙ 시간복잡도 생각 할 필요성이 있다. 헤매면서 여러가지 방식을 시도했지만, 결국 시간복잡도 크게 차이가 없었다.

---