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

 

 

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

 

문제 설명

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 primeArray = [Bool](repeating: true, count: n-1)
    var i = 2
    while i*i <= n {
        if primeArray[i-2] {
            stride(from:i*i, through: n, by: i).forEach{
                primeArray[$0-2] = false
            }
        }
        i += 1
    }
    return primeArray.filter{ $0 }.count
}

아무리 풀어도 시간초과가 나서 소수를 찾는 수학적 공식이 있나 싶어서 찾아보았더니 “에라토스테네스의 체”라는 소수를 찾는 빠르고 쉬운 방법이 있었다.

 

에라토스테네스의 체

소수를 찾는 가장 빠르고 쉬운 방법으로 에라토스테네스가 발견한 공식이다. 방법은 아래와 같다.

2부터 N까지의 나열된 수가 있다.

1. 여기서 2를 제외한 2의 배수를 찾아 소거시킨다. → 결과 : 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, …
2. 2의 배수를 소거시킨 배열에서 2의 그다음 수인 3을 제외한 3의 배수를 찾아 소거시킨다. → 결과 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, …
3. 2와 3의 배수를 소거시킨 배열에서 2와 3 다음 수인 5을 제외한 5의 배수를 찾아 소거시킨다. → 결과 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
4. 2와 3과 5의 배수를 소거시킨 배열에서 2, 3, 5 다음 수인 7을 제외한 7의 배수를 찾아 소거시킨다. → 결과 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
5. … 11
6. … 13
7. … 17

여기서 만약 N 이 소거시키는 값의 제곱보다 작다면, 소거시킬 값이 업으므로 종료한다.

예를 들어 N이 100이라고 했을 때 11의 제곱은 121이므로 100을 초과한다. 그러므로 7의 배수까지만 찾아 소거시켜도 1부터 100까지의 소수값을 찾을 수 있는 것이다.

그 어떤 방법보다 이 방법이 빨랐고, 나는 이 방법 그냥 습득하여 외우기로 했다.

 

 

다른 사람 풀이

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;
}

이 분은 배열을 만들어낸 뒤에 count 를 하지 않고 반복문을 실행하면서 소수의 갯수를 카운트 하였다. 배수를 false로 만드는 과정을 반복문을 사용해 구현하였다.

 

 

중요한 개념

• 소수를 구하기 위한 가장 빠른 방법은 에라토스테네스의 체