스위프트 - 프로그래머스 1. 소수찾기

출처

programmers.co.kr/learn/courses/30/lessons/12921

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

문제설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한사항

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

 

입출력 예

n	result
10	4
5	3

 

입출력 예 #1
1부터 10 사이의 소수는 [2, 3, 5, 7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2, 3, 5] 3개가 존재하므로 3를 반환

 

풀이

소수를 찾아 개수를 세어주는 문제이다. 요점은 1과 자기자신을 제외한 수로 나누었을 때 나머지가 0이 아니어야 되는데 전에 배웠을 땐 만약 숫자가 16 이라면 절반인 8까지만 순회해서 약수를 찾으면 되는걸로 기억했다.

 

근데 기억이 왜곡 되었었나보다 ㅎㅎ;; 주어진 숫자의 루트값 까지만 돌면 되는 거 같다. 1, 2, 4, 8, 16 이렇게 약수가 다 주어지면 끝까지 다 돌 필요가 없이 4까지만 돌면되기 떄문이다. 하지만!!! 주의할 점은 2 같은 경우는 루트 2까지 돌 수 없으므로 +1을 해준 값까지 순회처리를 해주었다. 그리고 1은 소수가 아니므로 범위에서 제외했다.

 

import Foundation     // sqrt 함수를 쓰기위해

func solution(n: Int) -> Int {
    var isPrime = true
    var cnt = 0
    
    for i in 2...n {
        isPrime = true
        
        // Double형으로 변환해야 sqrt 함수를 쓸 수 있고 for 문의 범위는 정수로 처리해야 하기 떄문에
        // 마지막에 Int로 다시 변환해줌
        for j in 2...Int(sqrt(Double(n))) + 1 {
            if i != j && i % j == 0 {
                isPrime = false
                break
            }
        }
        cnt = isPrime ? cnt + 1 : cnt
    }
    return cnt
}

print(solution(n: 16))