如何从 C 程序中的斐波那契数列中提取质数？

Question

我的大学考试有一道关于生成 FIB 序列并从结果中提取 PRIME 数的问题。我写了下面的代码，我得到了正确的结果。但是，我确定我的代码不干净。有人可以帮助我编写新代码或编辑我的代码并使其干净吗？

#include <stdio.h>

int main()
{
    int t1 = 0, t2 = 1, nextTerm = 0, n, i, position = 2, primeNumber[10], init = 2, count = 0;
    printf("Input N= ");
    scanf("%d", &n);

    printf("Fibonacci List: %d %d ", t1, t2);
    nextTerm = t1 + t2;

    while (nextTerm <= n)
    {
        printf("%d ", nextTerm);
        primeNumber[position] = nextTerm;
        position++;
        t1 = t2;
        t2 = nextTerm;
        nextTerm = t1 + t2;
    }

    printf("\nPrime numbers are ");
    position = 3;
    i = 1;
    init = 0;

    for (init = 1; init <= 7; init++)
    {
        for (i = 1; i <= primeNumber[position]; i++)
        {
            if (primeNumber[position] % i == 0)
            {
                count++;
            }
        }
        if (count == 2)
        {
            printf("%d ", primeNumber[position]);
        }
        count = 0;
        position++;
    }
    return 0;
}

Answer 1

首先，您的程序运行不适合我。它打印斐波那契列表然后中止。其他问题：

我不明白7从哪里来init <= 7 代码初始化init = 2，然后init = 0最后做init = 1 就在使用它之前！
你的素数检测逻辑做了比必要更多的工作——它测试了所有的除数，但是一旦找到第一个除数，测试就结束了，不需要测试其余的。您也未能将除数限制为平方根，您最终测试了所有小于目标的数字。
primeNumber[] 数组实际上填充的是斐波那契数，而不是素数，所以这个名字有误导性。它缺少索引检查，并且如评论中所述，并非绝对必要。

这是解决该问题的另一种简化方法：

#include <stdio.h>
#include <stdbool.h>

int main()
{
    unsigned n, f1 = 0, f2 = 1;
    printf("Input N = ");
    scanf("%u", &n);

    printf("Fibonacci List: %d %d ", f1, f2);

    for (unsigned f3 = f1 + f2; f3 <= n; f3 = f1 + f2)
    {
        f1 = f2;
        f2 = f3;

        bool is_prime = true; // assume it's prime until proven otherwise

        for (unsigned divisor = 2; divisor * divisor <= f3; divisor++)
        {
            if (f3 % divisor == 0)
            {
                is_prime = false;
                break;
            }
        }

        if (f3 > 1 && is_prime)
        {
            printf("[%d] ", f3);
        } else {
            printf("%d ", f3);
        }
    }

    printf("\n");

    return 0;
}

输出

% ./a.out
Input N = 10000
Fibonacci List: 0 1 1 [2] [3] [5] 8 [13] 21 34 55 [89] 144 [233] 377 610 987 [1597] 2584 4181 6765 
%

在没有数组的情况下，它一次输出斐波那契数和素数，序列中的素数用括号表示。

如何从 C 程序中的斐波那契数列中提取质数？

How to extract prime numbers from a fibonacci series in C program?

c

primes

fibonacci