Enhancing Performance of Sorted Linked List for Truncatable Prime Numbers

Question

I am currently engaged in solving Question 37 ("Truncatable Primes") on Project Euler. In essence, the task involves identifying 11 prime numbers with the unique property that, when any digit is removed from either the left or the right, the resulting number remains prime. For example, 3797 is such a prime because removing digits sequentially from the left or right (797, 97, 7, 379, 37, 3) produces prime numbers. Note:2,3,5,7 are not considered Truncatable for this specific question.

Initially, I implemented the algorithm in Python, and it executed efficiently in less than a second:

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))

Subsequently, I endeavored to implement the same algorithm in C. Due to the absence of a set datatype in C, I opted for a linked list with binary search. While the implementation is functional, it exhibited considerable slowness, running for approximately a minute. I am seeking insights into potential flaws in the overarching design and structure of my C code:

#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;
}

Any suggestions or critiques to enhance the performance of the C implementation is appreciated. Thanks in advance!

Answer 1

As your search can only traverse the linked list with statements like current = current->next; and current = current->previous;, there is no way you can do better than a linear search. The characteristic of a binary search is that you can jump to locations without having to visit the intermediate locations. That's an efficiency you cannot achieve with linked lists.

I would suggest an approach where you replace the set-idea from your Python code with a sieve, i.e. a boolean array that indicates whether the index is a number in the set or not. You need to allocate an array that is large enough for storing a boolean for all natural numbers up to some reasonable limit. Here we expect to find results with up to 6 decimal digits, so allocating a million entries (bytes) would be enough.

Here is an implementation of that idea:

#include <stdio.h>

// Must be a power of 10
#define SIEVE_SIZE 1000000
#define RESULT_SIZE 11

int main(void) {
    char sieve[SIEVE_SIZE];
    // Get all primes < SIEVE_SIZE: naive Eratosthenes sieve
    sieve[0] = sieve[1] = 1; // Not primes
    for (int i = 2; i < SIEVE_SIZE; i++) {
        if (!sieve[i]) { // Is prime?
            for (int j = i+i; j < SIEVE_SIZE; j += i) {
                sieve[j] = 1; // Not prime
            }
        }
    }
    // Main logic
    int sum = 0;
    int k = 0;
    for (int i = 11; i < SIEVE_SIZE; i++) {
        // Check for numbers with digits removed at the right side (including number itself)
        int j = i;
        while (j > 0 && !sieve[j]) {
            j = j / 10;
        }
        if (j) continue;
        // Check for numbers with digits removed at the left side
        j = SIEVE_SIZE / 10;
        while (j > 1 && !sieve[i % j]) {
            j = j / 10;
        }
        if (j > 1) continue;
        // Bingo
        printf("%d ", i);
        sum += i;
        if (k == RESULT_SIZE) {
            break;
        }
    }
    printf("\nsum = %d\n", sum);
    return 0;
}

This prints:

23 37 53 73 313 317 373 797 3137 3797 739397 
sum = 748317

Answer 2

There are several ways your code can be improved. All of the improvements except the first one are applicable to the Python version too.

1. Ditch the linked list, use an array. Your array is initially sorted, and you always add new primes at the end, so it remains sorted, and you can use the true binary search.
2. When testing primality, instead of checking all possible divisors, check only prime divisors. You already have them all.
3. Instead of testing that all truncations of a given prime are also primes, check that the two first truncations (one left and one right) are truncatable primes. You already have all smaller truncatable primes. You may even ditch the set of all primes altogether (but then you need to revert to your current primality test).
4. Instead of trying to test all numbers in order, try growing known truncatable primes (including, for this purpose, the single-digit ones). This one can be tricky to implement though.

Edit: #3 can also be problematic because as I just realized mixed truncations are not allowed. So you would need separate lists of left-truncatable and right-truncatable primes. This is not pretty.