斐波那契數列與質數生成：多語言基礎算法實現大全

斐波那契數列

定義：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。求第 n 項。

迭代法（O(n) 時間，O(1) 空間）

// Java
public static long fibonacciLoop(int n) {
    if (n <= 2) return 1;
    long a = 1, b = 1, c = 1;
    for (int i = 3; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

// C++
long long fib(int n) {
    if (n <= 2) return 1;
    long long a=1, b=1;
    for (int i=3; i<=n; ++i) {
        long long c = a + b;
        a = b; b = c;
    }
    return b;
}

矩陣快速冪（O(log n)）

// 矩陣 [[1,1],[1,0]]^n 的 [0][1] 元素即 F(n)
struct Mat { long long a[2][2]; };
Mat mul(Mat x, Mat y) {
    Mat r; memset(r.a,0,sizeof(r.a));
    for(int i=0;i<2;++i) for(int k=0;k<2;++k) for(int j=0;j<2;++j)
        r.a[i][j] = (r.a[i][j] + x.a[i][k]*y.a[k][j]) % MOD;
    return r;
}
Mat pow(Mat base, long long n) {
    Mat r; memset(r.a,0,sizeof(r.a)); r.a[0][0]=r.a[1][1]=1;
    while(n) { if(n&1) r=mul(r,base); base=mul(base,base); n>>=1; }
    return r;
}
long long fib_fast(long long n) {
    if (n<=2) return 1;
    Mat M; M.a[0][0]=M.a[0][1]=M.a[1][0]=1; M.a[1][1]=0;
    return pow(M, n-1).a[0][0];
}

通項公式（Binet 公式，浮點數精度有限）

F(n) = (φⁿ - ψⁿ) / √5,  φ=(1+√5)/2, ψ=(1-√5)/2

質數生成

試除法（O(n√n)）

// Java
public static void printPrimes(int n) {
    for (int i = 2; i < n; ++i) {
        boolean isPrime = true;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) { isPrime = false; break; }
        }
        if (isPrime) System.out.println(i);
    }
}

// C++
void printPrimes(int n) {
    for (int i=2; i

埃拉托斯特尼篩法（O(n log log n)）
// C++ 線性篩（O(n)）
vector primes;
vector is_composite;
vector lp; // 最小質因子

void linear_sieve(int n) {
    is_composite.assign(n+1, false);
    lp.assign(n+1, 0);
    for (int i=2; i<=n; ++i) {
        if (!is_composite[i]) { primes.push_back(i); lp[i] = i; }
        for (int p : primes) {
            if (p > lp[i] || i * p > n) break;
            is_composite[i*p] = true;
            lp[i*p] = p;
        }
    }
}

多語言對比表

語言
斐波那契(迭代)
質數(篩法)
特點
C/C++
極快，適合大 n 取模
bitset 優化內存
競賽首選
Java
BigInteger 支持大整數
BitSet 類
工程常用
Python
一行遞歸/生成器
列表推導式
原型驗證快
JavaScript
BigInt 支持
數組過濾
前端演示
Go
多返回值交換
切片操作
並發友好


總結
斐波那契數列與質數生成是程序設計入門的兩大基礎算法。掌握迭代、矩陣快速冪、通項公式三種斐波那契求解方式，以及試除法、埃氏篩、線性篩三種質數生成算法，能覆蓋從教學演示到高性能工程的各種場景。關鍵在於根據數據範圍選擇合適複雜度的算法，並注意整數溢出與精度問題。