Question

How to find a number that can be written as the sum and product of its factors in C

Answer 1

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DataStruct;

void ia_init(DataStruct *a) {
    a->size = 0;
    a->capacity = 8;
    a->data = malloc(a->capacity * sizeof(int));
}

void ia_push(DataStruct *a, int v) {
    if (a->size == a->capacity) {
        a->capacity *= 2;
        a->data = realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = v;
}

void ia_free(DataStruct *a) {
    free(a->data);
}

/* Simple ascending sort */
int cmp_int(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

/* Compute divisors of n */
void divisors(int n, DataStruct *out) {
    ia_init(out);

    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ia_push(out, i);
            if (i != n / i)
                ia_push(out, n / i);
        }
    }

    qsort(out->data, out->size, sizeof(int), cmp_int);
}

/* Check if n is a sum-product number */
int isSumProduct(int n, DataStruct *outFactors) {
    DataStruct d;
    divisors(n, &d);

    int a = 1, b = n;

    for (size_t i = 0; i < d.size; i++) {
        int x = d.data[i];
        if (x != 1 && x != n && n % x == 0) {
            a = x;
            b = n / x;
        }
    }

    ia_init(outFactors);
    ia_push(outFactors, a);
    ia_push(outFactors, b);

    long long product = (long long)a * b;
    long long sum = a + b;

    while (sum < product) {
        ia_push(outFactors, 1);
        sum++;
    }

    ia_free(&d);

    return sum == product;
}

int main(void) {
    for (int n = 5; n <= 14; n++) {
        DataStruct factors;

        if (isSumProduct(n, &factors)) {
            printf("%d = ", n);

            for (size_t i = 0; i < factors.size; i++) {
                printf("%d", factors.data[i]);
                if (i + 1 < factors.size) printf(" * ");
            }

            printf(" = ");

            long long sum = 0;
            for (size_t i = 0; i < factors.size; i++) {
                printf("%d", factors.data[i]);
                sum += factors.data[i];
                if (i + 1 < factors.size) printf(" + ");
            }

            printf(" = %lld\n", sum);
        }

        ia_free(&factors);
    }

    return 0;
}

 
 
/*
run:
 
6 = 3 * 2 * 1 = 3 + 2 + 1 = 6
8 = 4 * 2 * 1 * 1 = 4 + 2 + 1 + 1 = 8
9 = 3 * 3 * 1 * 1 * 1 = 3 + 3 + 1 + 1 + 1 = 9
10 = 5 * 2 * 1 * 1 * 1 = 5 + 2 + 1 + 1 + 1 = 10
12 = 6 * 2 * 1 * 1 * 1 * 1 = 6 + 2 + 1 + 1 + 1 + 1 = 12
14 = 7 * 2 * 1 * 1 * 1 * 1 * 1 = 7 + 2 + 1 + 1 + 1 + 1 + 1 = 14
 
*/
 

 

70+ SQL courses for beginners and professionals