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

以上是 C ++中的质数和斐波那契 的全部内容, 来源链接: utcz.com/z/316343.html

回到顶部