백준 알고리즘 1929번: 소수 구하기 C언어

문제 출처: www.acmicpc.net/problem/1929

1929번: 소수 구하기

1. 코드

#include <stdio.h>

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

2. 문제 해결 방식

먼저 배열의 인덱스 값을 이용하여 소수 판별을 하려고 한다. 그리고 값을 입력받고 해당하는 소수를 한 줄에 하나씩 출력할 것이다. 그렇다면 배열 arr의 0번째와 1번째는 1로 초기화를 한다. 1로 초기화를 하는 이유는 소수에 해당하는 수를 0으로 소수에 해당하지 않은 수를 1로 구분한다. 그렇다면 0과 1은 소수가 아니니 1로 초기화를 한 뒤에 진행한다.

 j를 2부터 시작하여 j < 1000001 / j라는 조건을 걸었는데 그 이유는 그 이상의 계산은 의미가 없기 때문이다. 예를 들어 2부터 100까지 소수인지 아닌지 판별한다고 가정해보자. 2를 제외한 2의 배수들은 판별하고 3을 제외한 3의 배수들은 판별하고 그렇게 9의 배수까지 가고 그렇다면 10의 배수 중에서 2부터 9의 곱들은 이미 소수를 판별하였다는 것이고 10 × 10만 남은 상황인데 총 100 이하의 수까지 파악하면 되기 때문에 100이 소수인지 판별하고 계산을 마친다. 마찬가지로 숫자가 100이 아니라 1000000이라도 같은 방식으로 계산을 이어가면 조금 더 효율적으로 반복문을 실행할 수 있다. 그리고 arr [ j ]의 값이 1이라면 continue문을 이용하여 불필요한 반복을 생략한다.

그리고 i의 값을 j * j로 하였는데 그 이유는 위에서 설명한 이유랑 같은데 j = 2일 때 i = 4이다. 그리고 2의 배수들을 판별을 완료하고 j = 3이고 i = 9인데 이때 3의 배수 중에 6도 있지만 2의 배수가 이미 판별을 했기 때문에 그다음의 배수를 판별해주면 된다. 그리고 증감식에서 i += j를 해준 이유는 굳이 1씩 증가하는 것보다 j값에 해당하는 배수에만 접근하는 것이 불필요한 반복을 막기 때문이다.

그렇다면 이제 0~1000000까지 소수들을 구했다. 문제에서 요구한 것은 한 줄에 하나씩, 증가하는 순서대로 소수를 출력하는 것인데 이미 배열과 배열의 인덱스 값을 이용하여 소수 판별을 완료한 상태이니 M부터 N까지의 배열 인덱스의 값이 소수인 것들을 출력하면 해결할 수 있다.

3. 느낀 점

소수 관련 문제를 푸는데 범위가 넓어지면 넓어질수록 반복문이 커지기에 조건문에 대해 많은 신경을 쓸 필요가 있었다. 생각보다 런타임 에러와 시간 초과가 나오지만 포기하지 않고 계속해서 문제를 풀어나가길 바란다.