백준 - 베르트랑 공준 4948번 c++

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

단계: 실버2

cpp 을 이용해 소수의 갯수를 파악하는 문제를 풀어보고자 했습니다.

 

 

 

처음에는 2부터 늘려가며 나누어지는지를 판단하는 방식으로 계산하였는데 시간초과로 인해 이러한 sequential한 방식이 아닌 다른 방식으로 해결하고자 했습니다.

#include <iostream>

using namespace std;


int main()
{
	int n = NULL;
	while (true)
	{
		cin >> n;
		if (n == 0) break;
		int count_num = 0;
		for (int i = n + 1; i <= 2 * n; i++)
		{
			bool get_out = false;
			if (i == 2 || i == 3)
			{
				count_num++;
				continue;
			}
			for (int j = 2; j < i; j++)
			{
				if (i % j == 0)
				{
					get_out = true;
					break;
				}
			}
			if (get_out==false) count_num++;
		}
		cout << count_num << endl;
	}
}

(시간초과 코드)

 

 

그래서 다음으로는 한번에 쭉 array를 만들어서 계산을 미리 하였다.

즉 매번 계산하지 않고 미리 소수인지 판별하였고 이를 즉시 사용하도록 했는데

다시 시간초과가 되었다.

#include <iostream>

using namespace std;

int main()
{
	int n = NULL;
	//max n is 123456
	int parr[246913] = { 0,0,1,1, }; // is 0,1,2,3 prime?

	for (int i = 3; i < 246913; i++)
	{
		bool is_prime{ true };

		for (int j = 2; j <= i/2; j++)
		{
			if (i % j == 0)
			{
				is_prime = false;
				break;
			}
		}
		if (is_prime) parr[i] = 1;
	}

	while (true)
	{
		cin >> n;
		if (n == 0) break;
		int count_num = 0;

		for (int check_num = n + 1; check_num <= 2 * n; check_num++)
		{
			count_num += parr[check_num];
		}
		cout << count_num << endl;
	}
}

(시간초과 코드2)

 

즉 애초에 이중 for문을 도는것 그 자체에서 문제가 있다고 생각했다.

	for (int i = 3; i < 246913; i++)
	{
		bool is_prime{ true };

		for (int j = 2; j <= i/2; j++)
		{
			if (i % j == 0)
			{
				is_prime = false;
				break;
			}
		}
		if (is_prime) parr[i] = 1;
	}

(이중 for문을 도는것 자체가 시간초과되는것이다.)

 

그런데 진짜 그런걸까...?

j를 i/2보다 작거나 같다는것을 설정하면서

그러면 1~9까지 하드코딩하면 j<=i/3으로 바꿀 수 있지 않을까? 생각이들었고

그러면 아예 안전하게 25까지로해서 j<=i/5로 확실하게 시간을 줄여보자는 생각을 했다.

하지만 그럼에도 시간초과가 떴다.

그런데 그럼 하드코딩할 필요 없이 지금까지 구하고 있는데 그다음에 쓰면 되는거 아냐? 라는 생각이 들었고

뒤늦게 j<=sqrt(i)로 만들 수 있다는 생각이 들었다.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	int n = NULL;
	//max n is 123456
	int parr[246913] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0, }; // is 0,1,2,...36 prime?

	for (int i = 26; i < 246913; i++)
	{
		bool is_prime{ true };

		for (int j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				is_prime = false;
				break;
			}
		}
		if (is_prime) parr[i] = 1;
	}

	while (true)
	{
		cin >> n;
		if (n == 0) break;
		int count_num = 0;

		for (int check_num = n + 1; check_num <= 2 * n; check_num++)
		{
			count_num += parr[check_num];
		}
		cout << count_num << endl;
	}
}

이렇게 살짝만 바꿔서 빅오 노테이션에서 n^2를 nlogn으로 줄였다.

 

간단한 문제라고 생각했는데 한시간 이상걸려서 풀게 되었다.