C語言經典練習：互滿數查找與快速排序實現

C語言進階練習：數論與排序算法實戰

練習一：互滿數/親和數查找 (3000以內)

若sumDiv(a)=b且sumDiv(b)=a (a≠b)，則(a,b)為互滿數對。

#include <stdio.h>
#include <math.h>

int sum_proper_divisors(int n) {
    if (n <= 1) return 0;
    int sum = 1;
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            sum += i;
            if (i != n/i) sum += n/i;
        }
    }
    return sum;
}
int main() {
    for (int a = 2; a < 3000; ++a) {
        int b = sum_proper_divisors(a);
        if (b > a && b < 3000 && sum_proper_divisors(b) == a)
            printf("%d %d\n", a, b);
    }
    return 0;
}

輸出：220 284、1184 1210、2620 2924 (3000以內僅三對)。

練習二：快速排序 (隨機數組驗證)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    quick_sort(a, l, i-1);
    quick_sort(a, i+1, r);
}
int main() {
    int a[N+1];
    srand(time(NULL));
    for (int i=1; i<=N; i++) a[i] = rand() % (N+1);
    quick_sort(a, 1, N);
    for (int i=1; i<=N; i++) printf("%d ", a[i]);
    return 0;
}

💡 核心技巧總結

1. 約數求和優化：只遍歷到√n，成對累加，避免重複。
2. 快速排序挖坑法：pivot挖出→右找小填左→左找大填右→遞歸。原地排序，空間O(log n)。
3. 隨機種子：srand(time(NULL))保證每次數據不同，驗證排序正確性。