[알고리즘] 백준 2581번 "소수" (C/C++) - Don 임베디드

문제 요약: 자연수 M과 N 이 주어질 때,

M이상 N 이하의 자연수 중 소수인 것을 합한 결과와,

이들 소수 중 최소값을 찾은 결과를 출력하라.

 

제약:

제한 시간 1초, 메모리 128MB

M,N <= 10000,

M <= N

 

예제 1 입력.	예제 1 출력.
60 100	620 61
예제 2 입력.	예제 2 출력.
64 65	-1

 

정답 코드:

 

#include <iostream>
 
using namespace std;
void _InitValues(bool bPrimeArr[], int nSize);    // 에라토스테네스의 체 함수 선언.
 
int main()
{
    int M, N;
    int nSum = 0;
    int nSmallestPrime = -1;
    bool bIsPrime[10001];    // 어떤 자연수 k가 소수인지 여부 bIsPrime[k]
 
    // 에라토스테네스의 체 함수 호출.
    _InitValues(bIsPrime, 10000);
 
    // 입력값.
    cin >> M >> N;
 
    for (int i = M; i <= N; i++)
    {
        if (bIsPrime[i] == true)
        {
            if (nSmallestPrime == -1)
            {
                nSmallestPrime = i;
            }
            nSum += i;
        }
    }
    
    if (nSmallestPrime == -1)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << nSum << endl;
        cout << nSmallestPrime << endl;
    }
 
    return 0;
}
 
void _InitValues(bool bPrimeArr[], int nSize)
{
    // 에라토스테네스의 체. 범위가 정해진 자연수 중 소수를 걸러낸다.
    int nCurrentNum;
 
    for (int i = 0; i <= nSize; i++)
    {
        bPrimeArr[i] = true;
    }
 
    // 1은 소수가 아님.
    bPrimeArr[1] = false;
 
    // 소수가 아닌 수들을 false 처리 해나간다.
    for (int j = 2; j <= nSize; j++)
    {
        if (bPrimeArr[j] == true)
        {
            // 소수인 경우, 자기 자신은 제외하고 시작.
            nCurrentNum = j * 2;
        }
        else
        {
            // 소수가 아닌 경우, 다음으로 이동
            continue;
        }
 
        // 소수인 경우 최대값에 도달할 때 까지 배수를 구하고, 모두 false 처리한다.
        while (nCurrentNum <= nSize)
        {
            bPrimeArr[nCurrentNum] = false;
            nCurrentNum += j;
        }
    }
}

원본 링크: https://www.acmicpc.net/problem/2581