JUNGOL 실력키우기 수학2 - 소수와 합성수 | 소수 | 소수 구하기 | 소수의 개수

기초 다지기에서 배운 내용을 응용하여 문제를 해결해야 하는 실력 키우기입니다.

실력 키우기는 비슷한 문제 유형별로 묶어서 풀어보겠습니다.

 

이번 포스팅에서는 수학2의 소수 시리즈를 풀어보겠습니다.

---

2811 : 소수와 합성수

 

이 문제는 단순하게 2부터 입력된 숫자까지를 돌면서 나눠지는 값이 있는지를 확인하여 나눠지는 경우 소수로 판단할 수도 있으나 조금 더 생각하면 범위를 줄일 수 있다는 것을 알 수 있습니다.

 

숫자를 나눌 수 있는 가장 큰 값은 해당 숫자의 루트 값 까지라는 것입니다.

 

즉, 2부터 해당 숫자까지를 나누는 게 아니라 해당 숫자의 루트까지만 나눠서 확인하면 되는 것입니다.

그렇게 하면 최대로 나누는 횟수는 10억 회가 아니라 10억의 루트 값인 31,622 회가 됩니다.

 

#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(int num);

int main(void)
{
	int num;
	for (int i = 0; i < 5; ++i)
	{
		cin >> num;
		if (num == 1)
		{
			cout << "number one" << endl;
		}
		else if (IsPrime(num))
		{
			cout << "prime number" << endl;
		}
		else
		{
			cout << "composite number" << endl;
		}
	}
}

bool IsPrime(int num)
{
	if (num < 2)
		return false;
        
	size_t limit{ static_cast<size_t>(sqrt(num)) };
	for (int i = 2; i <= limit; ++i)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=452&sca=2040

JUNGOL | 소수와 합성수 > 문제은행

 

1740 : 소수

 

이 문제도 이전에 만든 소수를 확인하는 함수를 사용해 소수인 경우 sum에 값을 누적하고 최초로 소수로 판정된 경우 최소 값으로 저장해 출력하면 됩니다.

 

마찬가지로 소수의 최솟값이 존재하지 않는다면 소수가 없는 것으로 판단해 -1을 출력하면 됩니다.

 

#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(int num);

int main(void)
{
	int m, n;
	cin >> m >> n;

	int sum{ 0 }, minPrime{ 10001 };
	for (int i = m; i <= n; ++i)
	{
		if (IsPrime(i))
		{
			sum += i;
			if (minPrime > 10000)
			{
				minPrime = i;
			}
		}
	}

	if (minPrime > 10000)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << sum << endl;
		cout << minPrime << endl;
	}
}

bool IsPrime(int num)
{
	if (num < 2)
		return false;

	size_t limit{ static_cast<size_t>(sqrt(num)) };
	for (int i = 2; i <= limit; ++i)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1013&sca=2040

JUNGOL | 소수 > 문제은행

 

1901 : 소수 구하기

 

이번 문제는 최대 값 까지의 소수를 구하고 주어진 값과 가장 가까운 소수를 찾아 출력하면 되는 문제입니다.

 

모든 소수를 구하는 방법은 에라토스테네스의 체라는 방법을 사용하면 되는데, 이것에 대해 간략하게 설명하자면 어떤 값이 소수일 때 그 값보다 크고 해당 값으로 나눠지는 수는 모두 합성 수라는 것을 알고 있으므로 미리 체크를 위한 배열을 만들어 소수를 찾았을 때 그 소수 이후에 해당 소수 값 간격의 모든 수를 합성 수로 체크하여 소수를 구하는 방법입니다.

 

#include <iostream>
#include <vector>

using namespace std;

void CalculatePrime();

bool checker[1000001]{};
vector<int> primeList;

int main(void)
{
	CalculatePrime();

	int n;
	cin >> n;

	int num;
	for (int i = 0; i < n; ++i)
	{
		cin >> num;

		int bigIndex{ 0 };
		for (int j = 0; j < primeList.size(); ++j)
		{
			if (primeList[j] > num)
			{
				bigIndex = j;
				break;
			}
		}

		int diffToBig{ primeList[bigIndex] - num };
		int diffToSmall{ (bigIndex > 0) ? num - primeList[bigIndex - 1] : diffToBig + 1 };
		
		int leastDiff{ (diffToBig < diffToSmall) ? diffToBig : diffToSmall };
		if (diffToSmall == leastDiff)
		{
			cout << primeList[bigIndex - 1] << ' ';
		}
		if (diffToBig == leastDiff)
		{
			cout << primeList[bigIndex] << ' ';
		}
		cout << endl;
	}
}

void CalculatePrime()
{
	for (int i = 2; i <= 1000000; ++i)
	{
		if (checker[i] == false)
		{
			primeList.push_back(i);
			for (int j = i * 2; j <= 1000000; j += i)
			{
				checker[j] = true;
			}
		}
	}
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1174&sca=2040

JUNGOL | 소수 구하기 > 문제은행

 

2813 : 소수의 개수

 

이 문제는 이전에 설명한 에라토스테네스의 체를 구할 때 나오는 체크용 배열로 쉽게 풀 수 있습니다.

체크가 된 값이 합성수이므로 체크가 되지 않은 경우 카운트를 세면 됩니다.

 

#include <iostream>

using namespace std;

void CalculatePrime();

bool checker[2000001]{};

int main(void)
{
	CalculatePrime();

	int n, m;
	cin >> n >> m;

	int primeCount{ 0 };
	for (int i = n; i <= m; ++i)
	{
		if (!checker[i])
		{
			primeCount++;
		}
	}

	cout << primeCount << endl;
}

void CalculatePrime()
{
	checker[1] = true;

	for (int i = 2; i <= 2000000; ++i)
	{
		if (checker[i] == false)
		{
			for (int j = i * 2; j <= 2000000; j += i)
			{
				checker[j] = true;
			}
		}
	}
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2079&sca=2040

JUNGOL | 소수의 개수 > 문제은행