[Swift] 프로그래머스 LV1. 소수 찾기

프로그래머스 LV1. 소수 찾기

 

✅ 소수 찾기 푸는데 나름 시간을 고려했다고 생각했는데 시간 초과가 남.

 

이런 친구들이 제일 화나면서 도전정신 들게 만드는데, 암튼 개선한거 같이 보자

 

func solution(_ n:Int) -> Int {
        // 소수찾는 알고리즘
        var count = 0
        var flag = true
        
        for target in stride(from: 3, through: n, by: 2) { // 어차피 짝수는 2말고는 다 소수 아님
            flag = true
            
//            print("target \(target)")
            
            for divisor in stride(from: 3, to: target, by: 2) {
//                print(divisor)
                if target % divisor == 0 {
                    flag = false
                    break
                }
            }
            
            if flag { count += 1 }
        }
        
//        print("")
        return count + 1
    }

효율성은 0점이군요 ㅎ

 

✅ [개선] 에라토스테네스의 접근

 

구글링을 하다가 이런 방법을 찾아서 해결함

func solution(_ n:Int) -> Int {
        // 소수찾는 알고리즘
        var count = 0
        var isPrime = true
        
        for target in stride(from: 3, through: n, by: 2) { // 어차피 짝수는 2말고는 다 소수 아님
            isPrime = true
            
            for i in stride(from: 2, through: sqrt(Double(target)), by: 1) {
                if target % Int(i) == 0 {
                    isPrime = false
                    break
                }
            }
            
            if isPrime { count += 1 }
        }
        
        return count + 1
    }
}

여기서 아래 코드 부분을 보면 되는데, sqrt로 만들어서 연산 횟수를 줄일 수 있었다.

for i in stride(from: 2, through: sqrt(Double(target)), by: 1)  { ... }

성공!

 

 

테스트 9번만 봐도 시간이 엄청나게 단축된 것을 확인할 수 있다