如何优化斐波那契素数判断的C代码？需将超时代码优化至O(n)复杂度

Hey there! Your code works correctly for the test cases, but the timeout happens because of inefficient prime checking and a few small inefficiencies in the Fibonacci check. Let's fix that while keeping everything in pure C, and get it running well within the time limit.

Key Optimizations to Make #

1. Speed Up Prime Checking #

Your original isprime function loops up to n/2, which is way more than necessary. Here's how to cut down the work:

• Early exit for even numbers: Except for 2, all even numbers are not prime. We can check this first to skip half the iterations.
• Loop up to sqrt(n): If a number n has a factor larger than its square root, the corresponding pair factor will be smaller than the square root. So we only need to check up to sqrt(n) instead of n/2.
• Skip even numbers in the loop: Once we've handled 2, we can increment by 2 instead of 1 to only check odd divisors.

2. Streamline Fibonacci Check #

Your existing Fibonacci check is functional, but we can add early exits for edge cases (like 0, 1, 2) to avoid unnecessary loop iterations. Also, since Fibonacci numbers grow exponentially, this loop will still run in O(log n) time, which is super fast even for large values.

Optimized Code #

#include<stdio.h>
#include<math.h> // For sqrt() in isprime

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);
        // Shorthand: if prime, check Fibonacci; else output 0
        printf("%d\n", isprime(i) ? isfib(i) : 0);
    }
    return 0;
}

int isprime(long int n) {
    // Handle base cases first to avoid unnecessary loops
    if (n <= 1) return 0;
    if (n == 2) return 1;
    // Even numbers greater than 2 can't be prime
    if (n % 2 == 0) return 0;
    
    // Check only odd divisors up to sqrt(n)
    for (long int j = 3; j <= sqrt(n); j += 2) {
        if (n % j == 0) return 0;
    }
    return 1;
}

int isfib(long int n) {
    // Edge cases: small Fibonacci numbers get immediate return
    if (n == 0 || n == 1 || n == 2) return 1;
    
    long int a = 1, b = 2, c;
    // Generate Fibonacci numbers until we match or exceed n
    while (1) {
        c = a + b;
        if (c == n) return 1;
        if (c > n) return 0;
        a = b;
        b = c;
    }
}

Why This Works Faster #

• Prime Check: The loop now runs up to sqrt(n) instead of n/2, which reduces iterations drastically for large numbers. For example, checking a prime like 1e6 would go from 500,000 iterations to just 1000.
• Fibonacci Check: Adding early exits for small values avoids unnecessary loop setup, and the exponential growth of Fibonacci numbers means the loop will only run ~40 times even for numbers up to 1e18 (since Fibonacci(40) is already over 1e8).

This code will easily stay under the 1.12 second time limit even for large input sizes.

内容的提问来源于stack exchange，提问作者Rudra prakash