Prime Factorization

by Mathias Van Malderen on Nov 8th, 2009

A program which displays the prime factors of a given number, all the 'hard' work is done by the factorize() function:

c Syntax (Toggle Plain Text)
/* Find out the prime factors
 * of a given number and print
 * them on the screen */
void factorize(int n)
{
  int d = 2;
 
  if(n < 2) return;
 
  printf("Prime factors of '%d': ", n);
  /* while the factor being tested
   * is lower than the number to factorize */
  while(d < n) {
    /* if valid prime factor */
    if(n % d == 0) {
      printf("%d x ", d);
      n /= d;
    }
    /* else: invalid prime factor */
    else {
      if(d == 2) d = 3;
      else d += 2;
    }
  }
 
  /* print last prime factor */
  printf("%d\n", d);
}
/* Find out the prime factors
 * of a given number and print
 * them on the screen */
void factorize(int n)
{
  int d = 2;
  
  if(n < 2) return;
  
  printf("Prime factors of '%d': ", n);
  /* while the factor being tested
   * is lower than the number to factorize */
  while(d < n) {
    /* if valid prime factor */
    if(n % d == 0) {
      printf("%d x ", d);
      n /= d;
    }
    /* else: invalid prime factor */
    else {
      if(d == 2) d = 3;
      else d += 2;
    }
  }
   
  /* print last prime factor */
  printf("%d\n", d);
}

It's working should be clear, anyways, I've included some comments here and there.
When adapted to C++, you could simply modify this code to store all the prime factors into a vector or something, for later reuse.
(in C, you can also do something equal, if you choose the appropriate data structure)

Some driver code is included, if you want the code to be run in test mode, you'll have to add the following line to the top of this program: #define TEST_DRIVER 1 .
This is my output when the program is run in test mode:

C Syntax (Toggle Plain Text)
Prime factors of '2': 2
Prime factors of '3': 3
Prime factors of '4': 2 x 2
Prime factors of '5': 5
Prime factors of '6': 2 x 3
Prime factors of '7': 7
Prime factors of '8': 2 x 2 x 2
Prime factors of '9': 3 x 3
Prime factors of '10': 2 x 5
Prime factors of '11': 11
Prime factors of '12': 2 x 2 x 3
Prime factors of '13': 13
Prime factors of '14': 2 x 7
Prime factors of '15': 3 x 5
Prime factors of '16': 2 x 2 x 2 x 2
Prime factors of '17': 17
Prime factors of '18': 2 x 3 x 3
Prime factors of '19': 19
Prime factors of '20': 2 x 2 x 5
Prime factors of '21': 3 x 7
Prime factors of '22': 2 x 11
Prime factors of '23': 23
Prime factors of '24': 2 x 2 x 2 x 3
Prime factors of '25': 5 x 5
Prime factors of '26': 2 x 13
Prime factors of '27': 3 x 3 x 3
Prime factors of '28': 2 x 2 x 7
Prime factors of '29': 29
Prime factors of '30': 2 x 3 x 5
Prime factors of '31': 31
Prime factors of '32': 2 x 2 x 2 x 2 x 2
Prime factors of '33': 3 x 11
Prime factors of '34': 2 x 17
Prime factors of '35': 5 x 7
Prime factors of '36': 2 x 2 x 3 x 3
Prime factors of '37': 37
Prime factors of '38': 2 x 19
Prime factors of '39': 3 x 13
Prime factors of '40': 2 x 2 x 2 x 5
Prime factors of '41': 41
Prime factors of '42': 2 x 3 x 7
Prime factors of '43': 43
Prime factors of '44': 2 x 2 x 11
Prime factors of '45': 3 x 3 x 5
Prime factors of '46': 2 x 23
Prime factors of '47': 47
Prime factors of '48': 2 x 2 x 2 x 2 x 3
Prime factors of '49': 7 x 7
Prime factors of '2': 2
Prime factors of '3': 3
Prime factors of '4': 2 x 2
Prime factors of '5': 5
Prime factors of '6': 2 x 3
Prime factors of '7': 7
Prime factors of '8': 2 x 2 x 2
Prime factors of '9': 3 x 3
Prime factors of '10': 2 x 5
Prime factors of '11': 11
Prime factors of '12': 2 x 2 x 3
Prime factors of '13': 13
Prime factors of '14': 2 x 7
Prime factors of '15': 3 x 5
Prime factors of '16': 2 x 2 x 2 x 2
Prime factors of '17': 17
Prime factors of '18': 2 x 3 x 3
Prime factors of '19': 19
Prime factors of '20': 2 x 2 x 5
Prime factors of '21': 3 x 7
Prime factors of '22': 2 x 11
Prime factors of '23': 23
Prime factors of '24': 2 x 2 x 2 x 3
Prime factors of '25': 5 x 5
Prime factors of '26': 2 x 13
Prime factors of '27': 3 x 3 x 3
Prime factors of '28': 2 x 2 x 7
Prime factors of '29': 29
Prime factors of '30': 2 x 3 x 5
Prime factors of '31': 31
Prime factors of '32': 2 x 2 x 2 x 2 x 2
Prime factors of '33': 3 x 11
Prime factors of '34': 2 x 17
Prime factors of '35': 5 x 7
Prime factors of '36': 2 x 2 x 3 x 3
Prime factors of '37': 37
Prime factors of '38': 2 x 19
Prime factors of '39': 3 x 13
Prime factors of '40': 2 x 2 x 2 x 5
Prime factors of '41': 41
Prime factors of '42': 2 x 3 x 7
Prime factors of '43': 43
Prime factors of '44': 2 x 2 x 11
Prime factors of '45': 3 x 3 x 5
Prime factors of '46': 2 x 23
Prime factors of '47': 47
Prime factors of '48': 2 x 2 x 2 x 2 x 3
Prime factors of '49': 7 x 7

That's it, enjoy!

Last edited by tux4life; Nov 8th, 2009 at 12:06 pm. Reason: fix a small code indenting issue

C Code Snippet (Toggle Plain Text)

#include <stdio.h>
 
/* Find out the prime factors
 * of a given number and print
 * them on the screen */
void factorize(int n)
{
  int d = 2;
 
  if(n < 2) return;
 
  printf("Prime factors of '%d': ", n);
  /* while the factor being tested
   * is lower than the number to factorize */
  while(d < n) {
    /* valid prime factor */
    if(n % d == 0) {
      printf("%d x ", d);
      n /= d;
    }
    /* invalid prime factor */
    else {
      if(d == 2) d = 3;
      else d += 2;
    }
  }
 
  /* print last prime factor */
  printf("%d\n", d);
}
 
#if defined TEST_DRIVER && TEST_DRIVER > 0
void factorize_test(void)
{
  int i;
  for(i = 0; i < 50; i++) {
	factorize(i);
  }
}
 
int main(void)
{
  factorize_test();
  return 0;
}
#else
int main(void)
{
  int number;
 
  do {
    printf("Enter number: ");
    scanf("%d", &number);
    factorize(number);
  } while (number > 1);
 
  return 0;
}
#endif