จำนวนเฉพาะและฟีโบนักชีใน 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