백준 알고리즘 2581번 : 소수 C언어

문제 출처: https://www.acmicpc.net/problem/2581

2581번: 소수

1. 코드

#include <stdio.h>

int main(void)
{
    int M, N, sum = 0, min = 0;
    int i, j, arr[10000] = {0, };
    
    arr[0] = 1, arr[1] = 1;
    for(j = 2; j < 10000/2; j++)
        for(i = j * j; i < 10000; i++)
            if(i % j == 0) arr[i] = 1;
    
    scanf("%d %d", &M, &N);
    
    for(i = M; i < N + 1; i++)
    {
        if(arr[i] == 0)
        {
            sum += i;
            if(min == 0) min = i;
        }
    }
    (sum == 0) ? printf("-1") : printf("%d\n%d\n", sum, min);
    return 0;
}

2. 문제 해결 방식

 접근 방식은 1978번 : 소수 찾기와 비슷하다. 우선 배열을 이용하여 소수 판별이 완료된 것을 정리하고 해당하는 수에 대한 계산을 하는 것인데 일단은 0번째와 1번째 배열은 1로 초기화를 한다. 왜냐하면 배열을 전체적으로 0으로 초기화하여 소수가 아닌 것은 1로 구분하고 소수가 맞은 것은 0으로 구분하기 위해서이다. 그리고 반복문을 사용하는데 2부터 배열의 최대 인덱스 값의 절반만큼만 반복한다. 그 이유는 해당하는 수는 제외할 것이기 때문이다. 예를 들어 2부터 시작하는데 2는 소수이다. 그렇다면 최소한 2의 2배의 수부터 소수 판별을 하는 것이 좋다. 이와 같은 맥락으로 배열의 인덱스 최댓값이 10000이므로 그것의 반인 5000의 2배부터 소수를 판별하기 때문에 의미가 없다고 생각한다.

그리고 i를 j * j부터 시작하는데 그 이유는 예시를 들어 설명해보겠다. j는 2부터 시작한다. 그렇다면 j * j는 4이다. 4부터 시작하여 10000까지 접근하여 2의 배수를 제거해준다. 그다음 수는 j는 3이다. 이미 3의 2배인 6은 방금 전 단계에서 이미 소수가 아니라고 판별했다. 그렇기 때문에 3의 2배에 대해서는 관심을 가질 필요가 없다. 그렇기에 3의 3배인 9부터 시작하여 10000까지 접근한다. 그다음도 똑같다. 4의 2 배수와 4의 3 배수는 이미 판별이 되었기에 4의 4 배수부터 시작해도 아무런 문제가 발생하지 않는다.

 이렇게 해서 1부터 10000까지 소수인지 아닌지 판별했다. 다음은 합계와 최솟값을 구하면 되는데 i를 M부터 시작한다. 그리고 N까지 실행하는데 배열의 인덱스 값이 소수라면 배열의 값은 0이다. 그렇기 때문에 해당하는 인덱스 값을 sum에 더하면 된다. 그리고 최솟값을 구해야 하기 때문에 처음에 소수인 것을 확인한 것을 min에 대입해야 하는데 조건문을 이용해 해결하자.  조건은 min이 0일 때 배열의 인덱스 값을 min으로 대입하는 것이다. 이렇게 한다면 제일 처음 발견하는 최솟값을 min에 저장할 수 있고, 추가적으로 min의 값을 변경할 수 없기 때문에 적합하다.

그리고 삼항 연산자를 이용하여 출력을 제어하는데 sum의 값이 0이라면 소수를 발견하지 못한 것이니 -1을 출력하고 만약 0이 아니라면 소수의 합계인 sum과 소수의 최솟값인 min을 출력해주면 이 문제를 해결할 수 있다.

3. 느낀 점

솔직히 문제는 어렵지 않았다. 하지만 1978번에서는 배열의 수가 적어서 시간이 많이 소요되지 않았지만 이 문제에서는 80ms를 소요해서 이 시간을 줄이기 위해 더 노력한 것 같다. 하지만 가까스로 해결되어서 다행이었다. 뭔가 수학 1도 그렇지만 수학 2도 어려우면서도 어려운 만큼 성취감도 커진다.

그리고 내가 이러한 문제에 깨달은 것을 글로 적으니 역시 조금 많이 길어지는 듯 하지만 나름 즐거웠다.