Today's Algorithm(2018-10-30)

programmers 소수의 합

소수를 이용하여 푸는 문제가 있을 때 가장 효율적인 방법은 '에라토스테네스의 체'를 이용하는 방법입니다. 이름은 어렵지만 구현이나 아이디어 자체는 크게 어렵지 않습니다. '에라토스테네스의 체'는 다음과 같이 구현할 수 있습니다.

1. 소수인지 아닌지 체크할 수 있는 배열을 하나 만들고 안에 boolean 값으로 true 를 모두 넣어둔다
2. 본격적으로 작업을 처리하기 전에 1보다 작거나 같은 수는 return처리하여 종료시킨다
3. 2부터 for문을 돌면서 해당 수가 소수 체크 배열에 true값인지 확인한다. true값이면 우선 그 수는 소수로 등록시키고, 그 수의 배수는 false 처리하여 이후 처리에서 제외시킨다

 

3번째 과정이 핵심이죠. 해당 수가 소수이면 그 수의 배수는 당연히 소수가 아니기 때문에(소수가 약수로 존재하므로) 제외하여 이후 연산 과정을 줄일 수 있습니다. 이를 바탕으로 문제 요구사항에 맞춰 구현하면 다음과 같습니다.

long long solution(int N) {
    bool d[N+1];  // 소수 체크할 수 있는 배열 생성
    long long answer = 0;

    if(N <= 1) {
        return 0;
    }

    for(int i = 2; i <= N; i++) {
        d[i] = true;  // 소수 체크할 수 있는 배열 true로 채워넣기
    }

    for(int x = 2; x <= N; x++) {
        if(d[x]) {  // 소수일 때
            answer += x;
            for(int y = x; y <= N; y += x) {  // 해당 소수의 배수는 false 처리
                d[y] = false;
            }
        }
    }
    return answer;
}

 아! 이번 문제의 경우 언어가 C++ 하나 밖에 제공되지 않아 Java대신 C++을 사용하였습니다.