[C++] 백준 4134. 다음 소수

문제

t개의 n을 입력받아 n보다 같거나 큰 소수의 최솟값을 출력하는 문제이다.

소수 판별

1. 2부터 n-1까지로 나눠보기

시간복잡도: O(n)

소수의 기본 개념을 갖다가 구현한 알고리즘이다.

코드1

for (int i = 2; i <= n - 1; i++) {
	if (n % i == 0) return false;
}

2. 2부터 √n까지 나눠보기

시간복잡도: O(√n)

어떤 수의 약수가 그 수에 루트 씌운 값을 기준으로 쌍을 이루는 규칙에서 고안된 알고리즘이다.
예를 들어 16의 약수는 1, 2, 4, 8, 16인데
16의 제곱근인 4를 기준으로 1-16, 2-8의 곱이 16으로 같게 쌍을 이룬다.

그래서 n-1까지 볼 필요 없이, √n까지만 확인해보면 된다.

코드2

#include <cmath>

for (int i = 2; i <= sqrt(n); i++) {
	if (n % i == 0) return false;
}

3. 에라토스테네스의 체

시간복잡도: O(Nlog(logN)

그리스 수학맨 에라토스테네스가 고안한 소수 판별 알고리즘이다.

1. 구하고자 하는 범위만큼 선언된 배열의 값을 모두 1(또는 true)로 초기화한다.
2. 0과 1(번째 값)을 0으로 만든다.
3. 2는 두고(1), 2의 배수를 모두 0으로 만든다.
4. 3는 두고(1), 3의 배수를 모두 0으로 만든다.
5. 4는 2의 배수에서 이미 정리됐다.
6. 5는 두고(1), 5의 배수를 모두 0으로 만든다.
7. again and again .. and agaain

구하고자 하는 값까지 이 과정을 반복한다.
배열[소수여부판별값] = 1이면 그 수는 소수라고 판별할 수 있다.

이해가 어렵다면 나무위키 정독을 추천한다.

코드3

#include <algorithm>

void getPrime(int n) {
	int *isPrime = new int[n+1];
	fill(isPrime, isPrime + (n + 1), 1);
	isPrime[0] = 0;
	isPrime[1] = 0;

	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {
			for (int j = i * 2; j <= n; j += i) {
				if (isPrime[j]) isPrime[j] = 0;
			}
		}
	}
}

풀이

n의 범위만 0부터 4*1e9로 나와있어서
t도 그냥 long long으로 잡고 풀었다.

저번에 확인하기론 그냥 int가 -2e9부터 2e9였고
unsigned int가 0부터 4e9여서 그거 쓰라는 것 같긴 했는데
타자 치기가 거스기해서 그냥 long long으로 선언했다.

최소공배수랑 최대공약수는 찾아본 다음에 기억이 났는데
소수 구하는 알고리즘은 뭔일인지 몰라도 딱 떠올랐다.

이 문제에서는 두 번째 알고리즘을 사용했다.

코드

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

long long t, n;

bool isPrime() {
	if (n <= 1) return false;
	
	for (long long i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) return false;
	}

	return true;
}

int main() {
	cin >> t;
	for (long long i = 0; i < t; i++) {
		cin >> n;
		while (!isPrime()) {
			n++;
		}
		cout << n << "\n";
	}

	return 0;
}

채점

자잘한 실수 때문에 원트에 풀진 못함시