소수 관련 문풀 (2581번, 4948번)

 

https://www.acmicpc.net/problem/2581

2581번: 소수

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int main()
{
	int m, n;
	cin >> m >> n;

	unsigned long sum = 0;
	vector<int> v;

	for (int i = m; i <= n; i++)
	{
		bool flag = true;
		if (i < 2)
			continue;
		for (int j = 2; j < i; j++)
		{
			if (i % j == 0)
			{
				flag = false;
				break;
			}
		}
		if (flag)
		{
			v.push_back(i);
			sum += i;
		}
	}
	if (sum == 0 || v.empty())
	{
		cout << -1;
		return 0;
	}
	cout << sum << '\n';
	cout << v.at(0);
	return 0;

}

그냥 소수 알고리즘인 에라토스테네스의 체를 사용안하고도 정답은 맞았다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int main()
{
	int m, n;
	cin >> m >> n;

	unsigned long sum = 0;
	vector<int> v;

	for (int i = m; i <= n; i++)
	{
		bool flag = true;
		if (i < 2)
			continue;
		for (int j = 2; j <= (int)sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = false;
				break;
			}
		}
		if (flag)
		{
			v.push_back(i);
			sum += i;
		}
	}
	if (sum == 0 || v.empty())
	{
		cout << -1;
		return 0;
	}
	cout << sum << '\n';
	cout << v.at(0);
	return 0;

}

제곱근까지만 해도 되므로 시간을 절약할 수 있다.

________________________________________________________________________________________________

 

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

갯수를 구하는 것이어서 vector에 일일이 값을 넣고 size를 찾는 것보단 그냥 int형 count를 선언해서 세주었다.

#include <iostream>
#include <cmath>

using namespace std;
int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n;
	cin >> n;
	while (n != 0)
	{
		int count = 0;
		for (int i = n + 1; i <= 2 * n; i++)
		{
			int rt = sqrt(i);
			bool flag = true;

			if (i == 1)
				continue;

			for (int j = 2; j <= rt; j++)
			{
				if (i % j == 0)
				{
					flag = false;
					break;
				}
			}
			if (flag)
			{
				count++;
			}
		}
		cout << count << '\n';
		cin >> n;
	}
    return 0;
}