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

실버Ⅴ

 

https://www.acmicpc.net/problem/2581

2581번: 소수

 

 

 

 

 

풀이 방법

 

우선 이 문제는 M과 N을 입력받고, M과 N 사이의 수 중 소수를 찾아 그 소수들을 모두 합한 값과, 그 소수 중 가장 작은 값을 각각 출력하는 문제이다.

 

먼저 나의 경우 N의 값을 입력받으면서 배열의 크기가 최대 N으로 고정되기 때문에 10000의 원소를 갖는 배열을 만드는 방법이 아닌, 동적할당을 이용해 배열을 할당했다. 

만약 동적할당의 사용법을 모른다면 동적할당에 관한 글을 아래에 링크로 남겨놓겠다.

https://bakjoon-coding.tistory.com/24

[C언어 기초] 메모리 동적할당(malloc)

 

 

소수를 구하는 방법의 경우, 에라토스테네스의 체 알고리즘을 이용해 소수를 구해보았다. 만약 에라토스테네스의 체 알고리즘을 잘 모른다면, 에라토스테네스의 체 알고리즘에 관한 글 역시 써 놓았다. 아래의 글을 보고 오면 된다.

https://bakjoon-coding.tistory.com/23

[알고리즘] 에라토스테네스의 체 알고리즘(C언어)

 

소수를 구하고 난 후에는 소수 중 최솟값과 소수들의 합을 구하였다.

 

내 코드

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
 
void Seive_of_Eratosthenes(int *arr, int N);
 
int main(void) {
    
    int M, N, i, *arr = NULL, sum = 0, flag = 0, Prime_min;
 
    scanf("%d %d", &M, &N);
 
    arr = (int*)malloc((N+1) * sizeof(int));
    if (arr == NULL)
        return -1;
 
    Seive_of_Eratosthenes(arr, N);
 
    for (i = M; i <= N; ++i) {
        if (arr[i] != 0) {
            //소수 중 최솟값
            if (flag == 0) {
                Prime_min = arr[i];
                flag = 1;
            }
            sum += arr[i];
        }
    }
 
    if (sum == 0)
        printf("-1\n");
    else
        printf("%d\n%d\n", sum, Prime_min);
 
    free(arr);
 
    return 0;
}
 
void Seive_of_Eratosthenes(int* arr, int N) {
    int i, j;
 
    for (i = 0; i <= N; ++i) {
        arr[i] = i;
    }
    arr[1] = 0;
 
    for (i = 2; i*i <= N; ++i) {
        if (arr[i] == 0)
            continue;
        for (j = i * 2; j <= N; j += i) {
            arr[j] = 0;
        }
    }
}

코드설명

 

#pragma warning(disable:4996)

Visual Studio에서 scanf 함수를 실행했을 때 발생하는 경고 메시지를 무시하기 위한 코드입니다.

 

 

#include <stdio.h>
#include <stdlib.h>

void Seive_of_Eratosthenes(int *arr, int N);

int M, N, i, *arr = NULL, sum = 0, flag = 0, Prime_min;

int형 변수 M, N, i, sum, flag, Prime_min을 선언합니다. arr은 포인터로 선언하고, NULL로 초기화합니다.

 

 

scanf("%d %d", &M, &N);

사용자로부터 M과 N을 입력받습니다.

 

arr = (int*)malloc((N+1) * sizeof(int));
if (arr == NULL)
    return -1;

 

Seive_of_Eratosthenes(arr, N);

Seive_of_Eratosthenes 함수를 호출하여 배열 arr에서 소수를 찾습니다.

for (i = M; i <= N; ++i) {
    if (arr[i] != 0) {
        //소수 중 최솟값
        if (flag == 0) {
            Prime_min = arr[i];
            flag = 1;
        }
        sum += arr[i];
    }
}
 

M부터 N까지의 숫자 중에서 소수를 찾아서 합과 최솟값을 구합니다.

 

 

if (sum == 0)
    printf("-1\n");
else
    printf("%d\n%d\n", sum, Prime_min);

sum이 0이면 -1을 출력하고, 그렇지 않으면 sum과 Prime_min을 출력합니다.

 

 

free(arr);

void Seive_of_Eratosthenes(int* arr, int N) {
    int i, j;
 
    for (i = 0; i <= N; ++i) {
        arr[i] = i;
    }
    arr[1] = 0;
 
    for (i = 2; i*i <= N; ++i) {
        if (arr[i] == 0)
            continue;
        for (j = i * 2; j <= N; j += i) {
            arr[j] = 0;
        }
    }
}

Seive_of_Eratosthenes 함수입니다. 에라토스테네스의 체 알고리즘을 이용하여 arr 배열에서 소수를 찾습니다.

먼저 arr 배열을 0부터 N까지 초기화합니다. 그리고 arr[1]을 0으로 설정합니다. 1은 소수가 아니므로, 소수가 아님을 표시하기 위해서 0으로 설정합니다.

i가 2부터 sqrt(N)까지 반복하는 동안, arr[i]가 0이 아니면(즉, 소수라면), i의 배수들을 0으로 설정합니다. 그리고 i를 증가시켜 다음 소수를 찾습니다.

예를 들어, i가 2일 때, arr[2]가 소수이므로, arr[4], arr[6], arr[8], ...을 0으로 설정합니다. 그리고 i를 3으로 증가시켜 다음 소수를 찾습니다.

이렇게 arr 배열을 모두 탐색하면, arr 배열에는 소수들이 0이 아닌 값으로 남게 됩니다.

 

 

느낀점

 

- 예전에 사용해보았던 에라토스테네스의 체 알고리즘을 다시 사용해보면서 복습할 수 있어서 좋았다.

- chatGPT가 내가 작성한 코드를 이렇게 잘 설명할 수 있을 줄은 몰랐는데 내가 작성한 의도에 맞게 설명하는 것을 보고 조금 놀랐따.

- 동적할당을 굳이 사용하지는 않아도 되지만, 사용해서 나쁠건 없다.