可截断素数问题的排序链表C实现性能优化咨询

问题背景 #

我正在解决Project Euler第37题「可截断素数」：需要找出11个特殊素数，要求从左侧或右侧依次移除任意数位后，所得所有数仍为素数（例如3797，截断后得到797、97、7、379、37、3，均为素数）。注意：2、3、5、7不被视为可截断素数。

Python实现（高效版） #

Python版本算法执行耗时不足1秒，代码如下：

l = []
p = {"","2","3","5","7"}

i = 11
while len(l) < 11:
    if all(i%j for j in range(2, int(i**0.5) + 1)):
        n = str(i)
        p.add(n)
        if all(n[:j] in p and n[j:] in p for j in range(1, len(n))):
            l.append(n)
            print(l)
    i += 2

print(sum(int(i) for i in l))

C语言实现（性能低下） #

尝试用C语言实现相同逻辑时，由于没有内置集合类型，采用了带二分搜索的双向链表存储素数。代码可正常运行，但耗时约1分钟，现寻求缺陷分析与优化建议：

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

#define TRUNCATABLE 11

struct Node {
    int val;
    struct Node *next;
    struct Node *previous;
};

bool search(struct Node *head, const int a, int listLength) {
    struct Node *current = head;

    int pos = 0;
    int left = 0;
    int right = listLength;

    while (current != NULL && left < right) {
        int mid = (left + right) / 2;
        while (pos < mid) {
            current = current->next;
            pos++;
        }
        while (pos > mid) {
            current = current->previous;
            pos--;
        }

        if (current->val < a) {
            left = mid + 1;
        } else if (current->val > a) {
            right = mid;
        } else {
            return true;
        }
    }
    return false;
}

void freeLinkedList(struct Node *head) {
    while (head != NULL) {
        struct Node *temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    struct Node *node2 = malloc(sizeof(struct Node));
    struct Node *node3 = malloc(sizeof(struct Node));
    struct Node *node5 = malloc(sizeof(struct Node));
    struct Node *node7 = malloc(sizeof(struct Node));

    node2->next = node3;
    node3->next = node5;
    node5->next = node7;
    node7->next = NULL;

    node2->previous = NULL;
    node3->previous = node2;
    node5->previous = node3;
    node7->previous = node5;

    node2->val = 2;
    node3->val = 3;
    node5->val = 5;
    node7->val = 7;

    struct Node *last = node7;
    struct Node *first = node2;

    int listLength = 4;

    int sum = 0;
    for (int i = 0, p = 11; i < TRUNCATABLE; p += 2) {
        int n = p;
        bool is_prime = true;

        for (int j = 2; j * j <= n; j++) {
            if (n % j == 0) {
                is_prime = false;
                break;
            }
        }

        bool is_trunc_prime = true;
        if (is_prime) {
            struct Node *new_node = malloc(sizeof(struct Node));
            last->next = new_node;
            new_node->previous = last;
            new_node->val = p;
            new_node->next = NULL;
            last = new_node;
            listLength++;
        }

        int digits = log10(n);
        while (is_trunc_prime && n > 10) {
            n /= 10;
            if (!search(first, n)) {
                is_trunc_prime = false;
                break;
            }
        }
        n = p;
        while (is_trunc_prime && digits > 0) {
            n = n % (int)pow(10, digits);
            if (!search(first, n)) {
                is_trunc_prime = false;
                break;
            }
            digits--;
        }
        if (is_prime && is_trunc_prime) {
            sum += p;
            i++;
        }
    }
    printf("%d\n", sum);
    freeLinkedList(node2);

    return 0;
}

C代码的性能缺陷分析 #

1. 链表结构完全浪费二分搜索优势：链表无法随机访问，每次二分查找时需要逐个移动指针到中间位置，导致搜索时间从理论上的O(logn)退化为O(n)，随着素数数量增加，耗时会急剧上升。
2. 素数判断逻辑重复低效：每次判断素数都从2遍历到sqrt(n)，没有利用已找到的素数列表优化因子判断，做了大量重复计算。
3. 浮点运算带来性能与精度问题：使用log10计算位数、pow生成取模值，不仅浮点运算速度远慢于整数运算，还可能因精度丢失导致错误（例如pow(10,3)可能返回999而非1000）。
4. 判断顺序不合理：无论当前数是否为素数，都会执行截断检查逻辑；且在将新素数加入链表后才进行截断验证，若截断不通过，链表插入操作属于无效开销。

性能优化建议 #

1. 用动态数组替代链表存储素数：数组支持随机访问，二分搜索可真正达到O(logn)时间复杂度，还能避免频繁的内存分配/释放操作。
2. 改用埃拉托斯特尼筛法预生成素数表：提前生成足够大的素数表（例如到100万，已知最大可截断素数为739397），素数判断和截断后的存在性检查都可通过O(1)数组查表完成，这是性能提升的核心优化点。
3. 用整数运算优化截断逻辑：右侧截断直接使用n /= 10；左侧截断通过预计算最高位权值实现，例如对于数p，先计算其最高位的10的幂次div，再通过p % div得到左侧截断结果，避免使用浮点函数。
4. 调整判断顺序，提前终止无效计算：素数判断后立即检查截断条件，一旦发现不符合就跳过后续操作，减少不必要的计算步骤。

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