C++의 소수와 피보나치

이 문제에서는 숫자 n이 주어집니다. 우리의 임무는 n보다 작거나 같은 모든 소수와 피보나치 수를 출력하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

Input: n = 30
Output: 2 3 5 13

설명

30보다 작은 피보나치 수는 1 1 2 3 5 8 13 21입니다.

이 숫자 중 소수는 2 3 5 13입니다.

이 문제를 해결하려면 n보다 작은 피보나치 수열의 모든 숫자가 소수인지 확인해야 합니다.

이를 위해 n보다 작거나 같은 모든 소수를 찾습니다. 그리고 생성된 숫자가 피보나치 수열에 포함되어 있는지 확인합니다.

숫자가 피보나치 수열에 있는 경우 , 5i2 + 4 또는 5i2 - 4 형식입니다.

솔루션 구현을 보여주는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;
bool isSquare(int n) {
   int sr = sqrt(n);
   return (sr * sr == n);
}
void printPrimeAndFibnacciNumbers(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) > 0 || isSquare(5*i*i-4) > 0))
      cout<<i<<"\t";
}
int main() {
   int N = 50;
   cout<<"All prime Fibonacci numbers less than "<<N<<" are :\n";
   printPrimeAndFibnacciNumbers(N);
   return 0;
}

출력

All prime Fibonacci numbers less than 50 are :
23513