Algorithm
Programers level1
[Swift] 소수 찾기
[Swift] 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
Example
Input: 10
Output: 4
Explanation: 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
Input: 5
Output: 3
Explanation: 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
문제 이해
- 1과 자기자신, 2개뿐이다.
코드
func solution(_ n:Int) -> Int {
var count = 0
if n == 1 {
return 0
}
if n == 2 {
return 1
}
for i in 2 ... n {
if isPrime(i) {
count += 1
}
}
return count
}
func isPrime(_ n: Int) -> Bool {
var i = 2
while i * i <= n {
if n % i == 0 {
return false
}
i += 1
}
return true
}
풀이
- 어떤 정수가 소수인지 판별하는 방법은 그 소수의 제곱근까지 나누어 보는 것
i * i <= n
- 여기가 효율성의 핵심이다.
- if == 1 은 발생하지 않지만 제약조건을 꼼꼼히 읽어보지 못했다.
다른 분의 멋진 코드
func solution(_ n:Int) -> Int {
var primes:[Bool] = [Bool](repeating:false, count:n+1);
var count = 0;
for i in 2...n {
if(!primes[i]){
count = count + 1;
}
for j in 1...(n/i) {
primes[i*j]=true;
}
}
return count;
}
잘 배웠습니다.
재귀를 사용하지 않고 풀고 싶었는데 멋진코드는 성공했다. dp 를 사용해 공간 사용이 크지만 소수 문제는 dp로 접근하는 것이 좋을 것 같다.
댓글남기기