[백준] 4948번: 베르트랑 공준

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

백준 4948번: 베르트랑 공준

 

초기 코드 (시간 초과)

#include <iostream>
using namespace std;

int main()
{
	int n;

	while (true)
	{
		cin >> n;

		if (n == 0)
		{
			break;
		}

		int count = 0; //소수 개수 카운트
		int temp = n;

		while (temp != 2*n)
		{
			bool check = true;

			for (int i = 2; i < temp; i++)
			{
				if (temp % i == 0)
				{
					check = false; //소수가 아니면 check=0
				}
			}

			if (check == true)
			{
				count++;
			}
			temp++;
		}
		cout << count << endl;	
	}
}

 

최종 코드

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
	int n;
	bool tempList[123456*2 + 1] = { 0, };

	while (true)
	{
		cin >> n;

		if (n == 0)
		{
			break;
		}

		int count = 0; //소수 개수 카운트
		int temp = n+1;
		
		while (temp <= 2*n)
		{
			bool check = true;

			if (tempList[temp] == 1)
			{
				count++;
				temp++;
				continue;
			}

			for (int i = 2; i <= sqrt(temp); i++)
			{
				if (temp % i == 0)
				{
					check = false; //소수가 아니면 check=0
					break; //이미 판정 끝나서 더 할 필요 없음
				}
			}

			if (check == true)
			{
				count++;
				tempList[temp] = 1;
			}
            
			temp++;
		}

		cout << count << endl;	
	}
}

에라토스테네스의 체의 원리를 활용해서 (아직 체를 정확히는 모름...)

: 제곱근까지만 for문을 돌아도 됨 (제곱근 위로는 어차피 제곱근 아래에 짝이 있어서 이미 소수가 아닌 것으로 판정)

그렇게 이미 구한 소수를 배열에 저장, 다음 번 판정에 활용하여 시간 단축