[프로그래머스 문제 풀이] 코딩테스트 연습 > 사용제 제작 문제 > 소수의 합

해당 문제와 채점 결과는 프로그래머스 사이트에 있는 내용이며 제가 작성한 부분은 프로그래머스 문제 풀이 입니다.

문제 설명

2부터 N까지의 모든 소수의 합을 구하세요.

N이 7이라면 {2, 3, 5, 7} = 17을 출력하시면 됩니다.

N의 범위는 2이상 10,000,000이하 입니다.

효율성 테스트의 모든 시간 제한은 1초입니다.

출제

본 문제는 엄주용 님이 제작해주신 문제입니다.

소수란?

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다.

소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.

출처 : 위키백과

제출한 코드 #1

#include <vector>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    bool isPrime;
    
    for( int i = 2; i <= N; i++ ) {
        isPrime = true;
        
        for( int j = 2; j < i; j++ ) {
            if(i % j == 0) {
                isPrime = false;
                break;
            }
        }
        
        if(isPrime) {
            answer += i;
        }
    }
    
    return answer;
}

채점결과 #1

일반적으로 소수구하는 로직을 넣어서 했는데 정확성 테스트는 모두 통과했으나 효율성 테스트에서 실패가 되는군요. 소수를 구하는데 다른 알고리즘이 있나 찾아보는데 에라토스테네스의 체라는 소수를 찾는 알고리즘이 존재하더군요.

에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

• 알고리즘
1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과

에라토스테네스의 체가 발견한 소수를 찾는 방법으로 다시 구현해서 풀어보겠습니다.

제출한 코드 #2 (에라토스테네스의 체 알고리즘)

    #include <vector>

    using namespace std;

    long long solution(int N) {
        long long answer = 0;
        bool *primeArray = new bool[N + 1];

        for(int i = 2; i <= N; i++) {
            primeArray[i] = true;
        }
        
        for(int i = 2; i * i <= N; i++) {
            if(primeArray[i]) {
                for(int j = i * i; j <= N; j += i) {
                    primeArray[j] = false;
                }
            }
        }
        
        for(int i = 2; i <= N; i++) {
            if(primeArray[i]) {
                answer += i;
            }
        }

        return answer;
    }

채점결과 #2 (에라토스테네스의 체 알고리즘)

우와.. 겁나게 빠르네요. 물론 소수를 구하는데 어떻게 코드를 짜는지는 정답이 없습니다. 어떻게 가든지 서울로만(?) 가면 되는 것이죠. 일단 자기만의 방법으로 문제를 풀어본 다음 다른 사람은 어떻게 코드를 작성했는지 보고 배울건 배우고 업그레이드 시킬건 업그레이드 시키고 자기자신의 것으로 흡수해서 발전시켜나가면 되겠습니다.

출처

• 프로그래머스 > 코딩테스트 연습 > 사용자 제작 문제 > 소수의 합 (바로가기, 새창)