백준 4948 c++ "베르트랑 공준" -PlusUltraCode-

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

 

[필자 사고]

소수를 구하는 문제이다. 

소수 구하는 방법은 여러개 있지마 대표적인 에스토라채 를 이용하여 해결했다.

알고리즘은 다음과 같다.

현재 숫자의 배수들은 반드시 소수가 아니다.

그래서 특정 숫자가 잡히고 그의 배수들은 모두 지워주는 형태로 문제를 해결했다.

 

아래는 자세한 코드해설이다.

[코드 해설]

 

2. Input() 함수

• arr 벡터의 크기를 MAX로 설정하고 모두 false로 초기화함.
  • 초기에는 모든 수를 소수로 가정함.

---

3. EstoraChae() 함수 (에라토스테네스의 체)

• 소수를 빠르게 판별하기 위한 에라토스테네스의 체 알고리즘을 구현함.
• 2부터 sqrt(MAX)까지 반복하면서:
  • 해당 숫자가 이미 합성수라면 건너뜀.
  • 아니라면 해당 숫자의 배수들을 모두 합성수로 표시(true) 함.
  • 배수는 i*i부터 시작하여 중복 제거 및 최적화를 함.

---

4. Game_Start(num) 함수

• 입력된 수 num에 대해 (num, 2n] 구간의 소수를 세는 함수.
• num+1부터 2*num까지 반복하면서, 그 숫자가 소수이면 개수를 증가시킴.
• 최종적으로 해당 범위 내 소수의 개수를 출력함.

---

5. main() 함수

• 먼저 Input()과 EstoraChae()를 호출하여 소수 판별 준비를 마침.
• 이후 무한 루프를 돌면서 정수 num을 입력받고:
  • num == 0이면 프로그램 종료
  • 아니라면 Game_Start(num)을 호출하여 소수 개수를 출력함.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 500000
using namespace std;

vector<bool> arr;

void Input() {
	arr.resize(MAX,false);
}

void EstoraChae() {
	
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (arr[i])continue;
		for (int k = i*i; k < MAX; k+=i) {
			arr[k] = true;
		}
	}
}

void Game_Start(int num) {
	int resultCount = 0;
	for (int i = num+1; i <= num * 2; i++) {
		if (arr[i] == false)resultCount++;
	}

	cout << resultCount << '\n';
}

int main(void) {
	Input();
	EstoraChae();
	int num;
	while (1) {
		int num;
		cin >> num;
		if (num == 0)break;
		Game_Start(num);
	}
}