c - 如何优化此代码？斐波那契素数代码？

Question

我的代码

#include<stdio.h>
int isprime(long int n);
int isfib(long int n);

int main()
{
    int t;
    long int i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%ld",&i);
        if(isprime(i))
        {
            printf("%d\n",isfib(i));
        }
        else
        {
            printf("0\n");
        }
    }
}

int isprime(long int n)
{
    int j;
    if(n==1)
    {
        return 0;
    }
    for(j=2;j<=n/2;j++)
    {
        if(n%j==0)
        {
            return 0;
        }
    }
    return 1;
}

int isfib(long int n)
{
   long int a=0,b=1,c=0;
    while(1)
    {
        c=a+b;
        if(c<n)
        {
          a=b;
          b=c; 
        }
        else if(c==n)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}

没有。测试用例。

输入 3 2 4

输出 1 1 0

代码正确。但我想以 O(n) 复杂度执行。

请问如何优化这段代码，我只想学习这种 C 编程语言的代码优化。

错误您的程序花费的时间比预期的要长。预计时间>1.12秒

Answer 1

对于初学者来说，isprime 的实现速度非常慢。这个要快得多:

int isprime(int n) {
    if(n == 1) return 0;
    int i=2;
    while(i*i<n) {
        if(n%i == 0)
            return 0;
        i++;
    }
    return 1;
}

我很确定您可以在网上找到类似的斐波那契数列。

但是，您似乎会收到相当多的数字。那么再次检查同一个号码就太浪费了。您可以使用以下想法来利用这一点。

int isprimeandsaveresult(int n, char * arr) {
    if(arr[n] == 1) return 1;
    if(arr[n] == 0) return 0;
    return arr[n] = isprime(n);
}

这里，arr 是一个巨大的数组，初始化为 1 或 0 以外的值。我选择 char 来节省内存，但这可以通过一些哈希函数进一步改进。您可以对斐波那契数使用相同的原理。