Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 해석
- Unity
- 일상생활 영어표현
- Java
- 논리 연산
- html
- 백준 2525번
- 5073번
- 배열
- 백준 1269번
- 백준 #11382번 #
- 백준 2587번
- 백준 27433번
- 상세 풀이
- javascript
- 연속된 숫자의 합
- 대칭 차집합
- 백준 2501번
- 피라미드 출력
- 백준 9506번
- 백준 5597번
- 백준 5086번
- 잡다한 일
- 차이
- 직각 삼각형
- 알고리즘
- 백준 25305번
- C
- C++
- 백준 1157번
Archives
- Today
- Total
YunDev
백준 2581번[C] - 상세 풀이 본문
https://www.acmicpc.net/problem/2581
#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;
}
풀이 : 이 문제의 핵심은 "에라토스테네스의 체" 알고리즘입니다. 이 알고리즘은 소수를 판별하기 위한 알고리즘으로,
간략하게 설명하자면
- 2부터 시작하여, 아직 지워지지 않은 수 중에서 가장 작은 수를 찾습니다.
- 그 수의 배수들을 모두 지웁니다.
- 더 이상 지워지지 않은 수가 없을 때까지 위 과정을 반복합니다.
이러한 과정을 통해 남아 있는 수는 소수입니다. 즉 소수의 배수들을 계속해서 지워나가는 방식입니다.(자기 자신 제외)
문제에서는 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 |