문제 개요
하나의 숫자 n이 주어졌을 때, n보다 작거나 같은 숫자 중에서 소수이면서 동시에 피보나치 수인 모든 값을 출력하는 것이 이 문제의 목표입니다.
예시
입력: n = 30
출력: 2 3 5 13
설명: 30 미만의 피보나치 수는 1, 1, 2, 3, 5, 8, 13, 21입니다. 이 중에서 소수에 해당하는 숫자는 2, 3, 5, 13입니다.
해결 접근 방법
이 문제를 해결하려면 n 이하의 피보나치 수열을 구성하는 숫자들 각각이 소수인지 확인해야 합니다. 가장 효율적인 접근 방법은 다음 두 단계로 나눌 수 있습니다.
- 소수 판별: 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 n 이하의 모든 소수를 먼저 구합니다.
- 피보나치 수 판별: 구해진 각 소수가 피보나치 수열에 포함되는지 확인합니다.
여기서 유용하게 활용할 수 있는 수학적 성질이 있습니다. 어떤 수 x가 피보나치 수라면, 5x² + 4 또는 5x² − 4가 반드시 완전제곱수(perfect square)가 됩니다. 이 성질을 이용하면 피보나치 수열을 직접 생성하지 않고도 해당 숫자가 피보나치 수인지 빠르게 판별할 수 있습니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 완전제곱수 여부를 확인하는 함수
bool isSquare(int n) {
int sr = sqrt(n);
return (sr * sr == n);
}
// 소수이면서 피보나치 수인 숫자를 출력하는 함수
void printPrimeAndFibonacciNumbers(int n) {
bool primeNumbers[n + 1];
memset(primeNumbers, true, sizeof(primeNumbers));
// 에라토스테네스의 체로 소수 판별
for (int p = 2; p * p <= n; p++) {
if (primeNumbers[p] == true) {
for (int i = p * 2; i <= n; i += p)
primeNumbers[i] = false;
}
}
// 소수이면서 피보나치 수인 경우만 출력
for (int i = 2; i <= n; i++)
if (primeNumbers[i] && (isSquare(5*i*i + 4) || isSquare(5*i*i - 4)))
cout << i << "\t";
}
int main() {
int N = 50;
cout << "50 이하의 소수 피보나치 수:\n";
printPrimeAndFibonacciNumbers(N);
return 0;
}
실행 결과
50 이하의 소수 피보나치 수:
2 3 5 13
코드 설명
isSquare(): 입력받은 숫자가 완전제곱수인지 확인합니다. 제곱근을 구한 뒤 다시 제곱했을 때 원래 값과 일치하는지 검사하는 방식입니다.printPrimeAndFibonacciNumbers(): 에라토스테네스의 체 알고리즘으로 n 이하의 소수를 먼저 걸러낸 후, 각 소수에 대해 5i² + 4 또는 5i² − 4가 완전제곱수인지 확인합니다. 두 조건을 모두 만족하는 숫자만 화면에 출력됩니다.
마무리
이 문제는 에라토스테네스의 체와 피보나치 수의 수학적 성질이라는 두 가지 고전적인 알고리즘 개념을 결합하여 효율적으로 해결할 수 있습니다. 소수 판별의 시간 복잡도는 O(n log log n)이고, 각 숫자의 피보나치 여부 확인은 O(1)이므로 전체적으로 매우 효율적인 알고리즘이라고 할 수 있습니다.