알고리즘/문제풀이

[백준] 2581 - 소수찾기(3)

무하지 2020. 12. 25. 21:38
반응형

문제 : www.acmicpc.net/problem/2581

 

2581번: 소수

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

www.acmicpc.net

 

 

이전 문제와 거의 똑같은 문제다.

 

이전 문제: 2020/12/25 - [프로그래밍/문제 풀이] - [문제풀이] 백준 1929번 - 소수찾기(2) {시간초과이슈}

 

[문제풀이] 백준 1929번 - 소수찾기(2) {시간초과이슈}

문제: www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acm..

lwamuhaji.tistory.com

 

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
32
33
34
35
#include<stdio.h>
 
int main() {
    int m, n;
    scanf_s("%d %d", &m, &n);
    bool* a = new bool[n + 1]; 
    //a[i]는 i가 소수인지 아닌지 알려준다.
    //a[i]가 true이면 i가 소수이고, false면 아니다.
 
    for (int i = 2; i < n + 1; i++)
        a[i] = true; //일단 모두 true로 초기화한다.
 
    for (int i = 2; i < n + 1; i++) {
        if (a[i]) { //만약 i가 소수라면
            for (int k = i * 2; k < n + 1; k += i) {
                a[k] = false;  //i의 배수는 모두 소수가 아니므로 false로 바꾼다.
            }
        }
    }
 
    int sum = 0, min;
 
    for (int i = m; i < n + 1; i++) {
        if (a[i]) { //만약 i가 소수라면
            if (sum == 0)
                min = i;
            sum += i;
        }
    }
 
    if (sum == 0)
        printf("-1");
    else
        printf("%d\n%d", sum, min);
}

cs

 

 

반응형