factors.h

View source code here on GitHub!

Includes

This file implements an Iterator that yields proper factors for a given number. It is generally used by first calling proper_divisor_count() and the next/next_p functions.

type factor_counter
uintmax_t (*iterator_function)(factor_counter *it)
bool exhausted : 1
bool started : 1
bool phase : 1
uintmax_t target
uintmax_t current
uintmax_t advance_factor_counter(factor_counter *fc)
void free_factor_counter(factor_counter fc)
factor_counter proper_divisors(uintmax_t target)
uintmax_t proper_divisor_count(uintmax_t target)
  1#pragma once
  2
  3#include <stdint.h>
  4#include "math.h"
  5#include "primes.h"
  6
  7typedef struct factor_counter factor_counter;
  8struct factor_counter   {
  9    IteratorHead(uintmax_t, factor_counter);
 10    size_t curr_index;
 11    size_t next_size;
 12    size_t batch_len;
 13    size_t factors_len;
 14    uintmax_t *current_batch;
 15    uintmax_t *prime_factors;
 16};
 17
 18void generate_combinations(
 19    const uintmax_t * const factors,
 20    const size_t factors_len,
 21    const size_t num_factors,
 22    uintmax_t *batch,
 23    const size_t max_combinations
 24) {
 25    size_t *indices = (size_t *) malloc(num_factors * sizeof(size_t));
 26    for (size_t i = 0; i < num_factors; i++)
 27        indices[i] = i;
 28    size_t batch_index = 0;
 29    while (batch_index < max_combinations) {
 30        uintmax_t product = factors[indices[0]];
 31        for (size_t i = 1; i < num_factors; i++)
 32            product *= factors[indices[i]];
 33        batch[batch_index++] = product;
 34
 35        size_t i = num_factors - 1;
 36        while (i < factors_len && indices[i] == factors_len - num_factors + i) {
 37            if (i == 0) {
 38                free(indices);
 39                return;
 40            }
 41            i--;
 42        }
 43        indices[i]++;
 44        for (size_t j = i + 1; j < num_factors; j++)
 45            indices[j] = indices[j - 1] + 1;
 46    }
 47}
 48
 49uintmax_t advance_factor_counter(factor_counter *fc) {
 50    IterationHead(fc);
 51    while (true) {
 52        if (fc->next_size == 0) {
 53            fc->next_size++;
 54            return 1;
 55        }
 56        while (fc->curr_index < fc->batch_len) {
 57            const uintmax_t ret = fc->current_batch[fc->curr_index];
 58            bool seen = false;
 59            for (size_t i = 0; i < fc->curr_index; i++)
 60                if (fc->current_batch[i] == ret) {
 61                    seen = true;
 62                    break;
 63                }
 64            fc->curr_index++;
 65            if (seen)
 66                continue;
 67            return ret;
 68        }
 69        const size_t num_factors = fc->next_size++;
 70        if ((fc->exhausted = (num_factors >= fc->factors_len))) return 0;
 71        fc->batch_len = n_choose_r(fc->factors_len, num_factors);
 72        fc->current_batch = (uintmax_t *) realloc(fc->current_batch, sizeof(uintmax_t) * fc->batch_len);
 73        fc->curr_index = 0;
 74        generate_combinations(fc->prime_factors, fc->factors_len, num_factors, fc->current_batch, fc->batch_len);
 75    }
 76}
 77
 78factor_counter proper_divisors(uintmax_t target) {
 79    factor_counter ret;
 80    IteratorInitHead(ret, advance_factor_counter);
 81    ret.next_size = 0;
 82    ret.curr_index = 0;
 83    ret.batch_len = 0;
 84    ret.current_batch = NULL;
 85    size_t written_len = 16;
 86    size_t curr_len = 0;
 87    ret.prime_factors = (uintmax_t *) malloc(sizeof(uintmax_t) * written_len);
 88    prime_factor_counter pfc = prime_factors(target);
 89    while (!pfc.exhausted) {
 90        if (curr_len >= written_len) {
 91            written_len *= 2;
 92            ret.prime_factors = (uintmax_t *) realloc(ret.prime_factors, sizeof(uintmax_t) * written_len);
 93        }
 94        ret.prime_factors[curr_len++] = next(pfc);
 95    }
 96    free_prime_factor_counter(pfc);
 97    ret.prime_factors = (uintmax_t *) realloc(ret.prime_factors, sizeof(uintmax_t) * curr_len);
 98    ret.factors_len = curr_len;
 99    return ret;
100}
101
102void free_factor_counter(factor_counter fc) {
103    if (fc.prime_factors != NULL)
104        free(fc.prime_factors);
105    if (fc.current_batch != NULL)
106        free(fc.current_batch);
107}
108
109uintmax_t proper_divisor_count(uintmax_t target);
110inline uintmax_t proper_divisor_count(uintmax_t target) {
111    uintmax_t ret = 0;
112    factor_counter fc = proper_divisors(target);
113    while (!fc.exhausted)
114        if (next(fc))
115            ret++;
116    free_factor_counter(fc);
117    return ret;
118}

Tags: factorization, divisor-count, c-iterator