[백준/BOJ] 4134번 다음 소수 (C/C++)

백준 온라인 저지(BOJ) 4134번 다음 소수
https://www.acmicpc.net/problem/4134

4134번: 다음 소수

* 사용언어 : C언어, C++
 

1. 문제

주어진 n개의 TC에 대해서
각 정수보다 크거나 같은 소수 중 가장 작은 소수 출력

 

2. 풀이

최대 40억의 숫자가 입력으로 주어지기 때문에
int가 아닌 unsigned int 나 long long int를 활용해야 합니다.
(int 범위 : 약 -21억 ~ 21억, unsigned int 범위 : 약 0 ~ 42억)
 
소수 여부를 판별할 때는 2부터 1씩 증가시키면서 나누어 떨어지는지를 확인하면 됩니다.
시간 절약을 위해 나누는 수는 n이 아닌 루트 n까지 진행합니다.
 

[소수 판별 시 루트 n까지만 확인하는 이유]
만약 어떤 수 n이 1과 n 외의 다른 수로 나누어 떨어진다면, n은 a * b로 표현할 수 있습니다.
이 때 a가 루트 n보다 크거나 같다면, b는 루트 n보다 작거나 같게 됩니다.

따라서 루트 n까지만 나머지 판별을 해도
b를 잡아낼 수 있기 때문에 충분히 n의 소수 여부를 확인할 수 있습니다.

 
해당 함수를 활용해서 +1씩 반복하여 크거나 같은 소수를 출력하도록 했습니다.
(소수가 아닌 0, 1인 경우 2로 고정 출력)
 
 
추가로 처음에 '에라토스테네스의 체'를 활용하여
40억 이하 모든 수에 대해 소수 여부를 확인한 후 시작하려 했었는데,
크기가 1 byte인 char 배열로 선언해도 3,814MB가 되어 메모리 초과로 진행할 수 없었습니다.
(char isPrime[4000000000])
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
4134_다음 소수
1128KB	100ms
*/
#include <cstdio>
#include <math.h>

unsigned int t, n;

int isPrime(unsigned int n) {
	int sq_n = int(sqrt(n)) + 1;
	for (int i = 2; i < sq_n; ++i) {
		if (n % i == 0) return 0;
	}
	return 1;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &t);
	while (t--) {
		scanf("%u", &n);

		if (n < 2) printf("2\n");
		else {
			while (1) {
				if (isPrime(n)) {
					printf("%u\n", n);
					break;
				}
				++n;
			}
		}
	}
	return 0;
}

* unsigned int 입출력 시 "%u"를 사용합니다.