백준 알고리즘 1978번 C언어

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

1978번: 소수 찾기

1. 코드

#include <stdio.h>

int main(void)
{
    int i, j, arr[1000] = {0, };
    int n, num, cnt = 0;
    
    arr[0] = 1, arr[1] = 1;
    
    for(j = 2; j < 1000; j++)
        for(i = j * 2; i < 1000; i++)
            if(i % j == 0) arr[i] = 1;
    
    scanf("%d", &n);
    
    for(i = 0; i < n; i++)
    {
        scanf("%d", &num);
        if(arr[num] == 0) cnt++;
    }
    printf("%d", cnt);
    return 0;
}

2. 문제 해결 방식

배열을 이용하여 처음부터 소수인 것들을 파악하고 그것들을 비교하여 판단하는 것이 편하다고 생각하여 풀기 시작하였다. 문제에서는 1000 이하의 수를 입력한다고 하니 배열의 크기를 1000의 크기로 선언하고 모든 값들을 0으로 한다. 그리고는 0번째와 1번째는 따로 1로 초기화를 해준다. 1로 초기화하는 이유는 소수가 아닌 값을 1로 구분하고 소수인 값을 0으로 구분하기 위해서이다.

그런데 또 다른 문제가 발생한다. 2는 소수이다. 하지만 2의 배수들은 소수가 아닌 것이다. 그렇다면 이를 해결할 수 있는 방법은 2의 배수에서부터 시작하면 문제가 없기에 2의 2배부터 해당하는 해당하는 값들을 1로 변환시켜주면 해결할 수 있다. 그리고 3의 배수, 4의 배수.... 등 같은 방식으로 풀어나가면 된다.

그리고 해당하는 수를 입력받고 소수 판별이 완료된 배열과 비교하여 배열의 값이 0이라면 cnt의 값을 증가시키고 최종적으로 모든 과정을 마친다면 합산된 cnt의 값을 출력하면 이 문제를 해결할 수 있다.

3. 느낀 점

그동안 사정이 있어서 문제를 못 풀고 있었다. 그래서 소수를 구하는 문제를 푸는 시간 최소 1~3시간은 걸릴 것 같다는 생각을 했지만 30분 만에 문제를 풀어서 생각보다 나 자신에게 놀랐다. 그래도 자만하지 않고 계속해서 꾸준하게 문제를 풀어나가야겠다.