Archive/Questions
[Programmers/Swift] 소수 찾기
Marco
2022. 4. 16. 21:48
728x90
programmers.co.kr - 코딩테스트연습 - Lv.2 - 완전탐색 - 소수 찾기
코딩테스트 연습 - 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상
programmers.co.kr
Constraints :
- n은 2이상 1000000이하의 자연수입니다.
//
// 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/
728x90