JUNGOL...55

Beginner_Coder/수학2/소수 구하기

---

문제                                            

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

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

 

입력 형식                                     

첫 번째 줄에는 처리해야 할 수의 개수 N을 입력 받는다. (N은 100이하의 정수)

다음 줄에는 처리해야할 수 N개(M1부터 Mn까지)를 한 줄에 한 개씩 차례로 입력 받는다. 

(Mi 는 1,000,000 이하의 양의 정수) 

데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

 

출력 형식                                     

임의의 값 Mi에 대해 차이가 가장 작은 소수를 구하여 출력한다.

만약 차이가 같은 소수가 여러 개이면 작은 수부터 모두 출력한다. 

출력되는 값은 1이상 1,000,000이하의 소수이어야 한다.

 

입력 예                                        

2

8

15

 

출력 예                                        

7

13 17

---

FindPrimeNumber.h

#include <iostream>

class FindPrimeNumber : public Base
{
private:
	bool IsPrimeNumber(int number);
	void PrintNearestPrimeNumber(int number);
};

 

FindPrimeNumber.cpp

void FindPrimeNumber::Code()
{
	int n;

	std::cin >> n;

	int number;
	for (int i = 0; i < n; i++)
	{
		std::cin >> number;
		PrintNearestPrimeNumber(number);
	}
}

bool FindPrimeNumber::IsPrimeNumber(int number)
{
	int limit{ static_cast<int>(std::sqrt(number)) };

	for (int i = 2; i <= limit; i++)
	{
		if (number % i == 0)
		{
			return false;
		}
	}
	return true;
}

void FindPrimeNumber::PrintNearestPrimeNumber(int number)
{
	int results[2]{};
	int arrDiff[2]{};
	int count{ 0 };
	int diff{ INT_MAX };

	for (int i = 2; ; i++)
	{
		if (IsPrimeNumber(i))
		{
			int temp{ std::abs(number - i) };
			if (temp <= diff)
			{
				diff = temp;
				if (count > 1)
				{
					results[0] = results[1];
					results[1] = i;

					arrDiff[0] = arrDiff[1];
					arrDiff[1] = diff;
				}
				else
				{
					results[count++] = i;
					arrDiff[count++] = diff;
				}
			}

			if (i > number)
			{
				break;
			}
		}
	}

	if (arrDiff[0] == arrDiff[1])
	{
		std::cout << results[0] << ' ' << results[1] << '\n';
	}
	else if (arrDiff[0] < arrDiff[1])
	{
		std::cout << results[0] << '\n';
	}
	else
	{
		std::cout << results[1] << '\n';
	}
}

 

---

실행 결과 Time Limit Exceed(70)

원인 매 계산 마다 모든 소수를 다시 계산하여 큰 수가 연속해서 들어오는 경우 모든 소수를 매번 계산하게 됨.

처리 방법 입력 되는 값까지의 소수를 미리 계산하여 저장 후 진행해야 함.

---

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Beginner_Coder/수학2/소수 구하기-JUNGOL