I’ve been learning a lot of computer science recently, which includes learning the syntax and idioms for many languages that are new to me. Recently I’ve been learning the C language. One thing I like to do when learning a new language is to have a few projects that I know how to write, and write a version of them in the new language. For me, these projects are implementing the bisection root finding algorithm, computing the Collatz sequence for a given number, and finding the factors of a number. These short projects are very easy to do, and can usually be done after only learning the language for an hour or so. Here, I want to go over how I wrote a factorizing function in C.

C is one of the oldest, most influential, and most popular programming languages used today. It is notorious for giving the programmer complete control over the program, and has no guardrails to help prevent you from doing things you probably don’t want. You can access an array of elements past the last one, point to memory wherever you want, or add a memory address to an integer. Many of these things that you are allowed to do are generally a bad idea, and will cause your program to crash or have unexpected behavior. As a result, you have to meticulously go over your program to ensure it will behave as expected.

I wanted to write a program that will print the factors of any integer. My factor function works like this:

int factor(unsigned long int n) {
  unsigned long int max = sqrt(n);
  for (unsigned long int i = 1; i <= max; i++) {
    if (n % i == 0) {
      if (!(i == max)) {
        printf("%lu %lu ", i, n / i);
      } else {
        printf("%lu ", i);
      }
    }
  }
  printf("\n");
  return 0;
}

I’m using the unsigned long int type to allow the program to factor the largest numbers available. The function takes a number $n$ as input and loops through the numbers less than it, checking if $n\equiv 0 \mod i$ for all $i$. If the number divides $n$, then it gets printed, along with it $n/i$, the complementary divisor to $i$. We only have to check up to $\sqrt{n}$, since any numbers larger than $\sqrt{ n }$ must correspond with another divisor less than $\sqrt{ n }$. The extra if statement just checks if the number is the square root of $n$, and only prints it one time if it is.

The main code works like this:

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("error: please enter a single integer beween 1 and %lu\n",
           ULONG_MAX);
    exit(EXIT_FAILURE);
  };
  if (*argv[1] == '-') {
    printf("error: enter a positive integer\n");
    exit(EXIT_FAILURE);
  }
  unsigned long int n;
  char *endptr;
  n = strtoul(argv[1], &endptr, 10);
  if (n <= 0) {
    printf("please enter an integer beween 1 and %lu\n", ULONG_MAX);
  };
  factor(n);
  exit(EXIT_SUCCESS);
}

I wanted the program to take an input from the command line, like factor 14. This is accomplished with argc and *argv[] in the functions parameters. argc is the number of parameters supplied, and *argv[] is an array of pointers that each point to the arguments that are passed to the function.

  if (argc != 2) {
    printf("error: please enter a single integer beween 1 and %lu\n",
           ULONG_MAX);
    exit(EXIT_FAILURE);
  };

This part ensures that only one argument is given to the function. If argc is not equal to 2, then we immediately terminate the program. argc should be 2, since the first argument is the program name and the second is the number.

Next we check that the number is positive

if (*argv[1] == '-') {
    printf("error: enter a positive integer\n");
    exit(EXIT_FAILURE);
  }

argv[1] is a pointer to the first character of what should be a number, so *argv[1] is the dereferenced value (the first character). If the first character is a ’-’, the program should immediately terminate.

The next part converts the string input into an integer, and checks that it’s not asked to factor 0. Then it just runs the factor function on the number:

unsigned long int n;
  char *endptr;
  n = strtoul(argv[1], &endptr, 10);
  if (n <= 0) {
    printf("please enter an integer beween 1 and %lu\n", ULONG_MAX);
  };
  factor(n);
  exit(EXIT_SUCCESS);

The full code is here:

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

int factor(unsigned long int n);

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("error: please enter a single integer beween 1 and %lu\n",
           ULONG_MAX);
    exit(EXIT_FAILURE);
  };
  if (*argv[1] == '-') {
    printf("error: enter a positive integer\n");
    exit(EXIT_FAILURE);
  }
  unsigned long int n;
  char *endptr;
  n = strtoul(argv[1], &endptr, 10);
  if (n <= 0) {
    printf("please enter an integer beween 1 and %lu\n", ULONG_MAX);
  };
  factor(n);
  exit(EXIT_SUCCESS);
}

int factor(unsigned long int n) {
  unsigned long int max = sqrt(n);
  for (unsigned long int i = 1; i <= max; i++) {
    if (n % i == 0) {
      if (!(i == max)) {
        printf("%lu %lu ", i, n / i);
      } else {
        printf("%lu ", i);
      }
    }
  }
  printf("\n");
  return 0;
}

I’m sure there are many improvements to be made, but this program can print the factors to the largest valid input, 18446744073709551615, in 5.042 seconds which is acceptable to me.