import Foundation
func solution(_ n:Int) -> Int {
var result = 0
for num in 2...n {
if isPrimeNumber(num) {
result += 1
}
}
return result
}
// 소수 판별 함수
func isPrimeNumber(_ n: Int) -> Bool {
if n < 2 {
return false
}
for i in 2..<Int(sqrt(Double(n)) + 1) {
if n % i == 0 { return false }
}
return true
}
- 2이상 n 제곱근 이하의 모든 수를 n으로 나눈 나머지가 0이 있는지 구하기
- 소수 판별 메서드 호출하여 소수인 경우 결과 +1
다른 사람의 풀이를 참고한 풀이
func solution(_ n:Int) -> Int {
var array = Array(repeating: 0, count: n+1)
var count = 0
for num in 2...n {
// 1. 이미 확인한 배열인지 확인 (소수일 때)
if array[num] == 0 {
// 2. 확인한 갯수 추가
count += 1
// 3. num의 배수인 배열의 인덱스를 1로 수정(소수가 아닌 합성수 제거)
for i in stride(from: num, through: n, by: num) {
array[i] = 1
}
}
}
return count
}
- 소수 판별 알고리즘 "에라토스테네스의 체" 방법 사용
"에라토스테네스의 체"
소수란 약수가 오로지 1과 자기자신 인 수. 즉, 1과 자기자신을 제외한 수의 배수가 되는 수는 소수가 아님 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법
1. 배열을 생성하여 초기화 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 제거 3. 2부터 시작하여 남아있는 수 모두 출력
