JUNGOL 실력키우기 1901 : 소수 구하기

 

소수(prime number)란 2이상의 수로써 1과 자기 자신 외에는 약수를 갖지 않는 수를 의미한다. 

임의의 M값에 대하여 M에 가장 가까운 소수를 구하는 프로그램을 아래 조건에 따라 작성한다.

첫 번째 줄에는 처리해야 할 수의 개수 N을 입력 받는다. (N은 100이하의 정수)
다음 줄에는 처리해야할 수 N개(M1부터 Mn까지)를 한 줄에 한 개씩 차례로 입력 받는다. (Mi 는 1,000,000 이하의 양의 정수)
데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

임의의 값 Mi에 대해 차이가 가장 작은 소수를 구하여 출력한다.
만약 차이가 같은 소수가 여러 개이면 작은수부터 모두 출력한다.
출력되는 값은 1이상 1,000,000이하의 소수이어야 한다.

[Copy] 2 8 15

[Copy] 7 13 17

 

---

 

이것도 마찬가지로 에라토스테네스의 체를 이용하여 소수를 구하여 그것을 활용하는 문제인데요,

저는 입력받은 수들 중 가장 큰 수보다 큰 소수까지를 구한 뒤,

그 소수들을 검사하여 현재 입력받은 수 보다 커지는 순간에 나타나는 소수 두개(더 큰 소수와 바로 직전의 소수)를 비교하여

더 작은 차이를 보이는 것을 출력하였고  이 차이값이 같은경우에는 순서대로 출력하도록 했습니다.

 

생각보다 오래걸렸네요. 아무래도 기초 로직을 몇 번 엎고 다시생각하니 오래걸린 것 같습니다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
// 최대 입력이 백만, 백만을 넘는 최소 소수는 백만삼
#define MAX_INPUT 1000005
// 전체를 검사하지 않기 위해 입력된 수에서 +ADD_NUM 까지만 검사하도록 한다.
#define ADD_NUM 200
 
// 소수와 합성수를 표현
enum { PRIME = 0, COMPOSIT = 1 };
 
void Initialize(int arr[], int N, vector<int>& prime);
void Eratos(vector<int>& prime, int max);
void PrintResult(int *arr, int N, vector<int>& prime);
 
int PrimeCheckArr[MAX_INPUT];
 
int main(void)
{
    vector<int> prime;
    int *arr;
    int N;
 
    cin >> N;
    arr = new int[N];
 
    Initialize(arr, N, prime);
    PrintResult(arr, N, prime);
 
    delete[] arr;
}
 
// 배열 값 초기화 함수
void Initialize(int arr[], int N, vector<int>& prime)
{
    int max = 0;
 
    for (int i = 0; i < N; ++i) 
    { 
        cin >> arr[i]; 
        // 입력 받는 수 중 최대값을 찾는다.
        if (arr[i] > max) max = arr[i];
    }
 
    // 소수를 구분하기 위한 배열을 초기화 해준다.
    for (int i = 0; i < max+ ADD_NUM; ++i)
        PrimeCheckArr[i] = i + 1;
 
    Eratos(prime, max);
}
 
void Eratos(vector<int>& prime, int max)
{
    // MAX_INPUT 만큼을 다 돌지 않고 작은 수가 들어온 경우 작은 범위만 돌도록 한다.
    for (int i = 1; i < max+ ADD_NUM; ++i)
    {
        if (PrimeCheckArr[i] == COMPOSIT) continue;
 
        // 소수인 경우 소수를 저장할 배열에 저장
        prime.emplace_back(PrimeCheckArr[i]);
 
        if (PrimeCheckArr[i] > max) break;
 
        // 이 소수의 배수들은 합성수이므로 제외
        for (int j = i + PrimeCheckArr[i]; j < max+ ADD_NUM; j += PrimeCheckArr[i])
        {
            PrimeCheckArr[j] = COMPOSIT;
        }
    }
}
 
void PrintResult(int *arr, int N, vector<int>& prime)
{
    int leftDiff, rightDiff;
    for (int i = 0; i < N; ++i)
    {
        int j;
        for (j = 0; j < prime.size(); ++j) 
        { 
            // 소수가 기준 값보다 크거나 같은 경우 
            // 가장 차이가 작은것은 그 소수이거나 바로 직전의 소수 두가지 경우
            if (prime[j] >= arr[i]) { break; }
        }
 
        // 기준 값 가까이에 있는 두 소수가 각각 얼마 차이나는지 저장
        leftDiff = arr[i] - prime[j-1];
        rightDiff = prime[j] - arr[i];
 
        // 차이값이 동일하면 작은 소수부터 출력
        if (leftDiff == rightDiff)
        {
            cout << prime[j - 1] << ' ' << prime[j] << endl;
        }
        // 그 외의 경우엔 차이값이 작은 소수를 출력
        else if (leftDiff < rightDiff)
        {
            cout << prime[j - 1] << endl;
        }
        else
        {
            cout << prime[j] << endl;
        }
    }
}

 

 

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