소수의 합

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

2부터 N까지의 모든 소수의 합을 구하세요.
N이 7이라면 {2,3,5,7} = 17을 출력 하시면 됩니다.
N의 범위는 2이상 10,000,000이하 입니다.
효율성 테스트의 모든 시간 제한은 1초입니다.

첫 시도

아주 무식한 방법이라 양시에 가책이 느겨졌지만, 그래도 일단 결과를 봐야겠다는 생각에 짰다.

#include <vector>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    for(int i = N; i > 1 ;i--){
        for (int j = 2; j <= i; j++){
            if(i==j){
                answer += i;
            }
            if(i%j == 0){
                break;
            }
        }
    }
    return answer;
}

결과

테스트 1
입력값 〉	7
기댓값 〉	17
실행 결과 〉	테스트를 통과하였습니다.

테스트 2
입력값 〉	8
기댓값 〉	17
실행 결과 〉	테스트를 통과하였습니다.

테스트 3
입력값 〉	2
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.

테스트 4
입력값 〉	2000000
기댓값 〉	142913828922
실행 결과 〉	코드 실행 중 오류가 발생하였습니다. 코드를 확인하세요. 실행 시간이 10.0초를 초과하여 실행이 중단되었습니다. 실행 시간이 더 짧은 다른 방법을 찾아보세요.

 

두 번째 시도

<위키피디아> 소수 찾기
현재까지 알려진 가장 간단한 방법으로 에라토스테네스의 체가 있다. 방법은 다음과 같다.
찾고자 하는 범위의 자연수를 나열한다. 2부터 시작하여, 2의 배수를 지워나간다.다음 소수의 배수를 모두 지운다.
이를 반복하여 마지막까지 지우면, 남는 수들이 소수가 된다. 이 과정은 사실 어떤 자연수 n이 소수임을 판정하기 위해서 floor(sqrt(n))까지만 진행하면 되는데, 수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 sqrt(n) 이하이기 때문이다. 소수를 골라내기 위한 방법은 다음과 같다. 이 방법을 이용해 소수를 어느 정도 골라낼 수 있다.
2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9이다.어떤 자연수 n이 소수임을 판정하기 위해선 sqrt(n)까지의 수 중 1을 제외하고 그 자연수의 약수가 있는 지 확인하면 된다. 배수의 성질을 이용하면 쉽게 구할 수도 있다. 그 외에도 다양하고 복잡한 판정법이 존재하지만, 위의 세 가지는 당연하고 간단한 것들이다.

위키피디아를 참고하여 소수를 찾는 방법인 "에라토스테니스의 체"를 이용하였다. 

 

#include <set>
#include <cmath>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    set<int> prime;
    set<int>::iterator iter;
    for(int i = 2; i <= N ; i++)
        prime.insert(i);
    
    int last= int(sqrt(N));
    for(iter = prime.begin(); iter != prime.end(); iter++){
        if(*iter > last)
            break;
        for(int i = 2; (*iter)*i <= N; i++){
            prime.erase((*iter)*i);
        }
    }
    
    for(iter = prime.begin(); iter != prime.end(); iter++){
        answer += *iter;
    }
    return answer;
}

결과

정확성 테스트

테스트 1 〉	통과 (0.22ms, 3.95MB)
테스트 2 〉	통과 (0.44ms, 3.83MB)
테스트 3 〉	통과 (0.69ms, 3.88MB)
테스트 4 〉	통과 (0.02ms, 3.78MB)
테스트 5 〉	통과 (0.04ms, 3.78MB)
테스트 6 〉	통과 (0.06ms, 3.75MB)
테스트 7 〉	통과 (0.08ms, 3.77MB)
테스트 8 〉	통과 (0.10ms, 3.89MB)

효율성 테스트

테스트 1 〉	통과 (725.54ms, 49.5MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

채점 결과

정확성: 40.0

효율성: 10.0

합계: 50.0 / 100.0

 

하지만 효율성 테스트에서 실패했다. 

 

 

세 번째 시도

Set의 자료구조는 binary tree이기 때문에 사실상 O(n*sqrt(n))이 아니라 여전히 Insert를 수행할 때, O(n^2)이라는 것을 깨달았다. 

따라서 자료구조를 vector로 변경하고, 데이터를 bool로 사용하여 경량화 하였다. 

#include <vector>
#include <cmath>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    vector<bool> isPrime;
    isPrime.assign(N+2, true);

    int last= int(sqrt(N));
    for(int i = 2; i <= last; i++){
        for(int j = 2; j*i <= N; j++){
            isPrime[j*i] = false;
        }
    }

    for(int i = 2; i <=N ; i++){
        if(isPrime[i])
            answer += i;
    }
    return answer;
}

 

결과

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.77MB)
테스트 2 〉	통과 (0.01ms, 3.79MB)
테스트 3 〉	통과 (0.02ms, 3.84MB)
테스트 4 〉	통과 (0.00ms, 3.76MB)
테스트 5 〉	통과 (0.00ms, 3.76MB)
테스트 6 〉	통과 (0.01ms, 3.77MB)
테스트 7 〉	통과 (0.00ms, 3.87MB)
테스트 8 〉	통과 (0.01ms, 3.85MB)

효율성 테스트

테스트 1 〉	통과 (8.04ms, 3.89MB)
테스트 2 〉	통과 (43.90ms, 3.93MB)
테스트 3 〉	통과 (112.69ms, 4.64MB)
테스트 4 〉	통과 (73.47ms, 4.77MB)

채점 결과

정확성: 40.0

효율성: 60.0

합계: 100.0 / 100.0

 

평가

  개인적으로 코딩 실력을 늘려야겠다는 의도의 첫 시도이다. 분명 많이 늦었다. 그리고 아직 무능한 것 역시 사실이다. 또한 나의 창의력으로 풀지 못하였다. 하지만 다른 면으로 바라보면 지금 시작한 것이 인생에서는 분명 빠른 것이다. 또한 모방을 통한 내재화를 이룬다면, 분명 성장할 것이라는 믿음을 갖어본다. 

 

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 다시 말해서 약수가 1과 자기 자신으로 이루어진 수이다. 

첫 번째 시도에서는 모든 수에 있어서 다 나누어 보면서 직접 약수를 확인하는 방식으로 하였기 때문에 O(n^2)의 time complexity이다.

두 번째 시도에서는 2부터 sqrt(n)까지의 수에 대하여 약수가 아닌 수를 하나씩 지워나간다. O(n*sqrt(n))의 time complecity를 갖는다. 하지만 자료구조 Set을 사용하면서 Insert가 여전히 O(n^2)의 time complecity를 갖는다. 

세 번째 시도에서는 vector를 사용하면서 O(n*sqrt(n))의 time complecity를 갖는다. 

 

자료구조 선택의 중요성을 깨달았다.