[C++] 뒤집은 소수

📄문제

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다.

첫 자리부터의 연속된 0은 무시한다.

뒤집는 함수인 int reverse(int x) 와 소수인지를 확인하는 함수 bool isPrime(int x)를 반드시 작성하여 프로그래밍 한다.

 

⬇️ 입력

첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.
각 자연수의 크기는 100,000를 넘지 않는다.

5 32 55 62 3700 250

 

⬆️ 출력

첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

23 73

 

📝 풀이

• 이 문제는 에라토스테네스의 체를 활용하여 풀 수 있습니다.

[C++] 에라토스테네스의 체

 

#include <iostream>

bool isPrime(int x);
int reverse(int x);

// 에라토스테네스의 체 알고리즘
static bool primes[100001];

int main()
{
	int N, numInput;
	scanf_s("%d", &N);

	// 모두 true로 초기화
	for (int i = 0; i < 100001; ++i)
		primes[i] = 1;

	// 0과 1은 소수가 아님
	primes[0] = primes[1] = false;

	// 에라토스테네스의 체 알고리즘을 통해 모든 소수 판별
	for (int i = 2; i <= std::sqrt(100001); ++i)
	{
		if (!primes[i])
			continue;

		primes[i] = true;
		for (int j = i * 2; j < 100001; j += i)
			primes[j] = false;
	}

	// 나머지 계산
	for (int i = 0; i < N; ++i)
	{
		scanf_s("%d", &numInput);

		int reverseNum = reverse(numInput);
		if (isPrime(reverseNum))
			printf("%d ", reverseNum);
	}
}

bool isPrime(int x)
{
	return primes[x];
}

int reverse(int x)
{
	int num = 0;

	while (x > 0)
	{
		num = num * 10 + x % 10;
		x /= 10;
	}

	return num;
}

• 큰 범위의 소수 문제는 에라토스테네스의 체를 이용하여 효율적으로 소수를 판별하였습니다.
• reverse 함수는 while문에서 첫번째 자리 값을 추출하여 더해주며 리턴합니다.