에미프(Emirp) 수란 무엇일까요?
에미프(Emirp) 수는 소수(prime number) 중에서 자릿수를 거꾸로 뒤집었을 때 또 다른 소수가 되는 특별한 수를 말합니다. 단, 이때 뒤집힌 수는 반드시 원래의 수와 달라야 합니다.
흥미롭게도 '에미프(Emirp)'라는 이름은 영어 단어 'prime(소수)'을 거꾸로 쓴 데서 유래했습니다.
에미프 수가 아닌 소수
모든 소수가 에미프 수인 것은 아닙니다. 다음과 같은 소수들은 에미프 수에서 제외됩니다.
- 회문 소수(Palindromic Prime): 11, 101처럼 뒤집어도 같은 수가 되는 소수
- 한 자리 소수: 2, 3, 5, 7처럼 한 자리로 이루어진 소수 (뒤집어도 자기 자신이 됨)
에미프 수의 예시
대표적인 에미프 수로는 13, 17, 37, 733 등이 있습니다. 예를 들어 13을 뒤집으면 31이 되는데, 31 역시 소수이므로 13은 에미프 수입니다.
n 이하의 모든 에미프 수 출력하기
이번 문제에서는 하나의 숫자 n이 주어졌을 때, n 이하의 모든 에미프 수를 찾아 출력하는 것이 목표입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: n = 40
출력: 13, 17, 31, 37
해결 접근 방법
주어진 수 이하의 모든 에미프 수를 찾으려면 다음 과정을 거칩니다.
- n 이하의 모든 소수를 구합니다.
- 각 소수의 자릿수를 뒤집은 수를 계산합니다.
- 뒤집힌 수가 원래 수와 다르면서 동시에 소수라면, 해당 수는 에미프 수이므로 출력합니다.
n까지의 소수를 빠르게 구하는 가장 효율적인 방법은 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하는 것입니다. 이 방법을 사용하면 짧은 시간 안에 범위 내의 모든 소수를 한 번에 판별할 수 있습니다.
C++ 코드 구현
앞서 설명한 솔루션의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int reverseDigits(int x) {
int digitRev = 0;
while (x > 0)
{
digitRev = (digitRev*10) + x%10;
x = x/10;
}
return digitRev;
}
void findAllEmirpNumber(int n) {
bool primeNo[10001];
memset(primeNo, true, sizeof(primeNo));
for (int p=2; p*p<=10001; p++)
{
if (primeNo[p] == true)
{
for (int i=p*2; i<=10001; i += p)
primeNo[i] = false;
}
}
for (int p=2; p<=n; p++)
{
if (primeNo[p])
{
int revNo = reverseDigits(p);
if (p != revNo && primeNo[revNo]) {
cout<<p<<"\t";
if(revNo <= n)
cout<<revNo<<"\t";
primeNo[revNo] = false;
}
}
}
}
int main()
{
int n = 40;
cout<<"All Emirp numbers less than or equal to "<<n<<" are\n";
findAllEmirpNumber(n);
return 0;
}
코드 동작 원리
- reverseDigits() 함수: 나머지 연산(%)과 나눗셈(/)을 반복하며 입력받은 수의 자릿수를 뒤집어 반환합니다.
- findAllEmirpNumber() 함수: 에라토스테네스의 체를 사용해 10,000 이하의 모든 소수를 미리 구해 둔 뒤, 2부터 n까지의 각 소수에 대해 자릿수를 뒤집은 값도 소수인지 검사합니다.
- 중복 출력 방지: 한 번 출력된 에미프 수(예: 13을 출력했다면 짝이 되는 31)는 primeNo 배열에서 false로 표시하여 같은 쌍이 두 번 출력되지 않도록 처리합니다.
실행 결과
All Emirp numbers less than or equal to 40 are 13 31 17 37