[백준] 24039번 - 2021은 무엇이 특별할까? (C++)

24039번: 2021은 무엇이 특별할까?

문제

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 주어진 수 N이 주어진다.

 

 

출력

첫 번째 줄에 N보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

 

 

풀이과정

입력값 보다 큰 값을 출력해라 다만 조건은 소수로 이루어진 값들이 * 형식으로 나와야한다 [n] * [n+1] 라는 문제였다

일단 소수들의 값을 구해두어야할 거 같아서 에라토스네스의 체 라는 알고리즘을 사용하여 소수들을 구했고,

문제에서 주어진 시간과 메모리가 넉넉해서 소수들을 바탕으로 경우의 수를 다 도는 방식을 사용하였습니다.

 

code

#include <iostream>
#include <vector>

const int	INF = 10001;

bool	arr[10001];

void	eratos()
{
	for (int i = 2; i <= INF; i++) {
		if (!arr[i]) {
			for (int j = i * i; j <= INF; j += i) {
				arr[j] = true;
			}
		}
	}
}

int		main(void)
{
	int n;
	std::vector <int> v;

	std::cin >> n;
	if (n == 1) {
		std::cout << "6" << "\n";
		return (0);
	}
	eratos();
	for (int i = 1; i <= INF; i++) {
		if (!arr[i]) v.push_back(i);
	}
	for (int i = 0; i < v.size(); i++) {
		if (v[i] * v[i + 1] > n) {
			std::cout << v[i] * v[i + 1] << "\n";
			break;
		}
	}

	return (0);
}

 

후기