JUNGOL 실력키우기 1740 : 소수

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오.

 

예를 들어 M=60, N=100이 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 

이들 소수의 합은 620이고, 최소값은 61이 된다.

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 같거나 작다.

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

[Copy] 60 100

[Copy] 620 61

 

---

 

이 직전 문제에서 힌트로 제공된 에라토스테레스의 채 방법을 이용하면 쉽게 해결이 가능합니다.

다만 문제를 제대로 안 읽어서 -1출력에 대한 처리를 안해서 한번 틀렸네요.

나름 가독성을 높이기 위해서 여러가지로 실험하고 있는데 제대로 되고 있는건지는 모르겠군요.

 

 

#include <iostream>
 
using namespace std;
 
// 소수와 합성수를 표현
enum { PRIME = 0, COMPOSIT = 1 };
 
void Initialize(int arr[], int N);
void Eratos(int* arr, int M, int N, int *sum, int *min);
void PrintResult(int &sum, int &min);
 
int main(void)
{
    int *arr;
    int M, N;
    int sum, min;
 
    sum = min = 0;
 
    cin >> M >> N;
 
    arr = new int[N];
    Initialize(arr, N);
 
    Eratos(arr, M, N, &sum, &min);
    PrintResult(sum, min);
 
    delete[] arr;
}
 
// 배열 값 초기화 함수
void Initialize(int arr[], int N)
{
    for (int i = 0; i < N; ++i)
    {
        arr[i] = i + 1;
    }
}
 
// 포인터(*) 대신 참조자(&)를 사용해도 됩니다.
void Eratos(int* arr, int M, int N, int *sum, int *min)
{
    for (int i = 0; i < N; ++i)
    {
        // 합성수인 경우 제외함 + 1은 소수도 합성수도 아니니 제외
        if (arr[i] == COMPOSIT) continue;
 
        // 이 소수의 배수들은 합성수이므로 제외
        for (int j = i + arr[i]; j < N; j += arr[i])
        {
            arr[j] = COMPOSIT;
        }
 
        // 범위 안에 포함되는 경우 값을 더한다.
        // 그 중 처음 포함되는 것이 최소값이니 따로 저장한다.
        if (arr[i] < M) continue;
        if (arr[i] > N) continue;
        if (*min == 0) *min = arr[i];
        *sum += arr[i];
    }
}
 
// 결과를 출력한다.
void PrintResult(int &sum, int &min)
{
    if (min == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << sum << endl;
        cout << min << endl;
    }
}
 

 

 

JUNGOL) 문제은행) 실력키우기) 소수