Prime Factorization

tux4life 0 788 Views

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

/* 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:

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!

sdfghjk commented: MOTHER FUCKER +0 
#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
Member Avatar for William Hemsworth
William Hemsworth 1,339 Posting Virtuoso

Nice, neat, consistent format, and well commented code :]

Member Avatar for nonlinearly
nonlinearly 0 Newbie Poster

wrong d=25 is not prime!

Member Avatar for deceptikon
deceptikon 1,790 Code Sniper

wrong d=25 is not prime!

How is it wrong? The program doesn't say that 25 is prime.

Member Avatar for nonlinearly
nonlinearly 0 Newbie Poster

it makes an assumption that all odd numbers are prime numbers (d += 2) if I understand well... correct me if I am wrong...

Member Avatar for deceptikon
deceptikon 1,790 Code Sniper

it makes an assumption that all odd numbers are prime numbers (d += 2) if I understand well... correct me if I am wrong...

It's the other way around. The function makes the assumption that all even numbers are not prime, which is a safe assumption given that 2 (the only even prime) is given special treatment. The d += 2 part of this algorithm is skipping over even numbers (excluding 2) because they're guaranteed not to be prime factors.

Member Avatar for delta_frost
delta_frost 0 Newbie Poster

Yes deceptikon is right and in addition to that,you need not check till the number itself,just check till the sqaure-root of the number and store it in an array and accordingly print them in sorted order.

Edited by delta_frost
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview