YunDev

백준 2581번[C] - 상세 풀이 본문

Programming/Baekjoon Program

백준 2581번[C] - 상세 풀이

S준 2024. 1. 18. 21:03

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

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net


#include <stdio.h>

int main() {
  int M, N, tmp, min_prime = -1;
  int check[10000] = {0,};
  int sum = 0; 
  scanf("%d %d", &M, &N);
    
    	//에라토스테네스의 체 알고리즘(소수는 0, 아니라면 1)
        for(int i = 2; i <= N; i++) {
            if(check[i] == 0) {
                if(i >= M) {
                    sum+=i;
                    if(min_prime == -1) {
                        min_prime = i;
                    }
                }
                for(int j = i*i; j <= N; j+=i) {
                 check[j] = 1;
            }
        }
    }
 
    if(min_prime != -1) {
        printf("%d\n%d", sum, min_prime);
    }
    else{
        printf("-1");
    }

    return 0;
}

풀이 : 이 문제의 핵심은 "에라토스테네스의 체" 알고리즘입니다. 이 알고리즘은 소수를 판별하기 위한 알고리즘으로,
간략하게 설명하자면 

  1. 2부터 시작하여, 아직 지워지지 않은 수 중에서 가장 작은 수를 찾습니다.
  2. 그 수의 배수들을 모두 지웁니다.
  3. 더 이상 지워지지 않은 수가 없을 때까지 위 과정을 반복합니다.

이러한 과정을 통해 남아 있는 수는 소수입니다. 즉 소수의 배수들을 계속해서 지워나가는 방식입니다.(자기 자신 제외)
문제에서는 M~N사이의 소수의 합을 구해야하므로 2부터 시작하여 소수가 아닌 수들은 모두 1로 바꾸고, 소수는 모두 0으로 정해집니다.  그리고 소수의 합을 나타내는 sum은 현재 i가 M 이상일 때부터 소수의 합을 계산합니다.
이렇게 소수의 총합을 구하고 나서는 소수의 최솟값을 계산해야합니다. 소수의 최솟값은 min_prime에 담겨지게 되는데,
min_prime에는 -1을 대입하고 만약 M이상의 소수가 처음으로 나왔을 때 min_prime에 값을 대입하여 최솟값을 구하는 방식입니다. 따라서 만약 M~N사이의 소수가 하나도 없다면 그대로 -1이 담겨지기 때문에 조건문을 통해 -1을 출력합니다. 
소수의 최솟값이 하나로 정해질 수 밖에 없는 이유는 min_prime에 최솟값을 대입한 이후에는 (min_prime == -1) 이라는 조건에 맞지 않기 때문에 더 이상 참이 될 수 없기 때문입니다.



'Programming > Baekjoon Program' 카테고리의 다른 글

백준 5086번[C] - 상세 풀이  (0) 2024.01.20
백준 1978번[C] - 상세 풀이  (1) 2024.01.19
백준 2839번[C] - 상세 풀이  (0) 2024.01.17
백준 2501번[C] - 상세 풀이  (0) 2024.01.16
백준 25305번[C] - 상세 풀이  (1) 2024.01.15