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

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

2581번: 소수

 

 

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

 

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

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

 

#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);
}