[Programmers/Swift] 소수 찾기

programmers.co.kr - 코딩테스트연습 - Lv.2 - 완전탐색 - 소수 찾기

코딩테스트 연습 - 소수 찾기

Constraints :

• n은 2이상 1000000이하의 자연수입니다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/04/16.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

// 구버전 - 시간초과
func solution(_ n:Int) -> Int {
    return (2...n).filter({ (i: Int) -> Bool in
        return (2..<i).filter({ i%$0==0 }).isEmpty
        }).count
}

// 신버전
func solution(_ n:Int) -> Int {
    var nonPrimes = [Bool](repeating: false, count: n + 1), result = 0
    
    for num in 2...n {
        if !nonPrimes[num] {
            for multi in stride(from: num, through: n, by: num) {
                nonPrimes[multi] = true
            }
            result += 1
        }
    }
    
    return result
}

print(solution(10)) // 4
print(solution(5)) // 3

How I tried this :
역시 복습의 중요성

 

프로그래머스 측에서 문제 조건을 바꾼듯했다.

기존 코드가 시간초과가 나서.. 고민을 많이 했다.

 

보통 기존 문제 풀이 할때는 소수 처리되는 부분을 빼고 나머지를 처리하는 형태였는데.

에라토스테네스의 체 

 

생각이 나서 동시에 적용했다.

 

What I got is :

var multi = 1
            
while multi * num <= n {
   nonPrimes[multi * num] = true
   multi += 1
}
            
---

for multi in stride(from: num, through: n, by: num) {
   nonPrimes[multi] = true
}

처음엔 while 위처럼 코드를 짰는데 아래처럼 stride도 다른 분 답을 보고 참고해보았다

문제에 관한 모든 저작권 : https://programmers.co.kr/