[프로그래머스 LV.1] 소수 찾기

프로그래머스 LV.1 모음

소수 찾기

문제 설명

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을 반환

---

제출

import Foundation

func solution(_ n:Int) -> Int {
  var isPrime = true
  var count = 0

  for i in 2...n {
    isPrime = true

    for j in 2...Int((sqrt(Double(n))))+1 {
      if i != j && i % j == 0 {
        isPrime = false
        break
      }
    }

    count = isPrime ? count + 1 : count
  }

  return count
}

2부터 n까지 i를 증가시키며 반복문을 실행한다.
2부터 n의 제곱근까지 반복문을 실행하며, i와 j가 같거나 i가 j로 나누어 떨어지면 소수가 아니므로 isPrime 변수를 false로 바꾼다.
그리고 반복문을 종료시킨다.
isPrime 변수가 true라면 1을 증가하고, 아니라면 증가하지 않는다.

다른 풀이

import Foundation

func solution(_ n:Int) -> Int {
    var array = Array(repeating: true, count: n+1)
    var result = 0
    
    for i in 2...n where array[i] == true{
        result += 1
        for j in stride(from: i, through: n, by: i){
            array[j] = false
        }
    }
    
    return result
}

n개의 요소를 갖는 Bool 배열 array를 생성한다.
2부터 n까지 i를 증가시키며 반복문을 실행하며, array[i]가 true인 경우만 구문을 실행한다.
j를 i부터 n까지 i만큼 증가시키며 반복문을 실행하며, array[j]를 모두 false로 만든다.

ex) n이 10, i 가 2인 경우 2, 4, 6, 8이 모두 false가 되며, 이후 반복문에서 2의 배수는 구문을 동작하지 못한다.