[Swift Algorithm] 소수 찾기 Programmers(Lv.1)

문제 설명

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

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

 

제한 조건

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

 

입출력 예

n	result
10	4
5	3

 

내 문제 풀이

func solution(_ n:Int) -> Int {
    var result = 0 // 소수의 개수 담기 위한 변수
    var answer = true // 소수인지 아닌지 판별하기 위한 변수
    
    for i in 2...n {
        // 2, 3은 어차피 소수고
        // 제곱근까지 나누기 위해서 제곱근이 2보다 작은 2, 3은 따로 빼서 result에 개수를 더해주었음
        if i < 4 {
            result += 1
        }
        
        else {
            // i를 2부터 i의 제곱근까지 차례로 나눠보는 for문
            for j in 2...Int(sqrt(Double(i))) {
                // i가 한 번이라도 나눠져 떨어진다면 그 수는 소수가 아니기 때문에 바로 break
                if i % j == 0 {
                    answer = false
                    break
                }
                
                // i가 나눠져 떨어지지 않는다면 answer에 true 저장
                else {
                    answer = true
                }
            }
            
            // 반복문 종료 후 answer가 true일 경우 해당 수는 소수로 판별, result에 1 추가
            if answer == true {
                result += 1
            }
        }
    }
    
    return result
}

• 2, 3은 어차피 소수기 때문에 n이 4보다 클 때는 2, 3에 대한 부분을 카운트해주었다.
• 주어진 수의 제곱근까지 반복하며 주어진 수를 나누어주었다. 
  (어차피 제곱근까지도 나눠지지 않았다면 더이상 나눠질 수가 없기 때문.)
• Bool 변수로 소수인지 아닌지 판별하여 횟수를 카운트했다.
  
  

💡 피드백

• 입력이 4 미만일 때를 따로 빼줬는데,
  2일수도 있고 3일수도 있는데 그 케이스를 디테일하게 만들어주지 않은 것이 아쉬운 듯 하다.
• 전체적으로 코드가 좀 길고 정리되지 않은 느낌,, 개선이 필요하다.

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

import Foundation

func solution3(_ n:Int) -> Int {
    var count = 2
    
    if n == 2 { return 1 }
    else if n == 3 { return 2 }
    else {
        for i in 4...n {
            var isPrime = true
            for j in 2...Int(sqrt(Double(i))) {
                if i%j == 0 { isPrime = false; break }
            }
            if isPrime == true { count += 1 }
        }
    }
    return count
}

• 입력이 2일 때, 3일 때를 따로 빼주어 횟수를 카운트 해주었다.
• 입력이 4 이상일 때 부터는 입력된 수를 제곱근까지로 나누어 소수를 판별해주었다.
• 판별은 Bool 값으로 해주었고, true일 경우 횟수를 추가해주는 방식으로 작성했다.
• 첫 번째 풀이와 비슷하지만 2, 3일 때 케이스를 잘 정리해준 것 같다. 

 

---

 

 

문제

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