C RSS C RSS

Prime Factorization

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
tux4life tux4life is offline Offline 30 Days Ago, 11:57 am |
0
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) 
  1. /* Find out the prime factors
  2.  * of a given number and print
  3.  * them on the screen */
  4. void factorize(int n)
  5. {
  6.   int d = 2;
  7.  
  8.   if(n < 2) return;
  9.  
  10.   printf("Prime factors of '%d': ", n);
  11.   /* while the factor being tested
  12.    * is lower than the number to factorize */
  13.   while(d < n) {
  14.     /* if valid prime factor */
  15.     if(n % d == 0) {
  16.       printf("%d x ", d);
  17.       n /= d;
  18.     }
  19.     /* else: invalid prime factor */
  20.     else {
  21.       if(d == 2) d = 3;
  22.       else d += 2;
  23.     }
  24.   }
  25.  
  26.   /* print last prime factor */
  27.   printf("%d\n", d);
  28. }
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) 
  1. Prime factors of '2': 2
  2. Prime factors of '3': 3
  3. Prime factors of '4': 2 x 2
  4. Prime factors of '5': 5
  5. Prime factors of '6': 2 x 3
  6. Prime factors of '7': 7
  7. Prime factors of '8': 2 x 2 x 2
  8. Prime factors of '9': 3 x 3
  9. Prime factors of '10': 2 x 5
  10. Prime factors of '11': 11
  11. Prime factors of '12': 2 x 2 x 3
  12. Prime factors of '13': 13
  13. Prime factors of '14': 2 x 7
  14. Prime factors of '15': 3 x 5
  15. Prime factors of '16': 2 x 2 x 2 x 2
  16. Prime factors of '17': 17
  17. Prime factors of '18': 2 x 3 x 3
  18. Prime factors of '19': 19
  19. Prime factors of '20': 2 x 2 x 5
  20. Prime factors of '21': 3 x 7
  21. Prime factors of '22': 2 x 11
  22. Prime factors of '23': 23
  23. Prime factors of '24': 2 x 2 x 2 x 3
  24. Prime factors of '25': 5 x 5
  25. Prime factors of '26': 2 x 13
  26. Prime factors of '27': 3 x 3 x 3
  27. Prime factors of '28': 2 x 2 x 7
  28. Prime factors of '29': 29
  29. Prime factors of '30': 2 x 3 x 5
  30. Prime factors of '31': 31
  31. Prime factors of '32': 2 x 2 x 2 x 2 x 2
  32. Prime factors of '33': 3 x 11
  33. Prime factors of '34': 2 x 17
  34. Prime factors of '35': 5 x 7
  35. Prime factors of '36': 2 x 2 x 3 x 3
  36. Prime factors of '37': 37
  37. Prime factors of '38': 2 x 19
  38. Prime factors of '39': 3 x 13
  39. Prime factors of '40': 2 x 2 x 2 x 5
  40. Prime factors of '41': 41
  41. Prime factors of '42': 2 x 3 x 7
  42. Prime factors of '43': 43
  43. Prime factors of '44': 2 x 2 x 11
  44. Prime factors of '45': 3 x 3 x 5
  45. Prime factors of '46': 2 x 23
  46. Prime factors of '47': 47
  47. Prime factors of '48': 2 x 2 x 2 x 2 x 3
  48. Prime factors of '49': 7 x 7
That's it, enjoy!
Last edited by tux4life; 30 Days Ago at 12:06 pm. Reason: fix a small code indenting issue
Show Printable Version Show Printable Version
Quick reply to this message  
Code Snippet
•
•
•
•
C Syntax
Toggle Plain Text
  1. #include <stdio.h>
  2.  
  3. /* Find out the prime factors
  4.  * of a given number and print
  5.  * them on the screen */
  6. void factorize(int n)
  7. {
  8.   int d = 2;
  9.  
  10.   if(n < 2) return;
  11.  
  12.   printf("Prime factors of '%d': ", n);
  13.   /* while the factor being tested
  14.    * is lower than the number to factorize */
  15.   while(d < n) {
  16.     /* valid prime factor */
  17.     if(n % d == 0) {
  18.       printf("%d x ", d);
  19.       n /= d;
  20.     }
  21.     /* invalid prime factor */
  22.     else {
  23.       if(d == 2) d = 3;
  24.       else d += 2;
  25.     }
  26.   }
  27.  
  28.   /* print last prime factor */
  29.   printf("%d\n", d);
  30. }
  31.  
  32. #if defined TEST_DRIVER && TEST_DRIVER > 0
  33. void factorize_test(void)
  34. {
  35.   int i;
  36.   for(i = 0; i < 50; i++) {
  37. 	factorize(i);
  38.   }
  39. }
  40.  
  41. int main(void)
  42. {
  43.   factorize_test();
  44.   return 0;
  45. }
  46. #else
  47. int main(void)
  48. {
  49.   int number;
  50.  
  51.   do {
  52.     printf("Enter number: ");
  53.     scanf("%d", &number);
  54.     factorize(number);
  55.   } while (number > 1);
  56.  
  57.   return 0;
  58. }
  59. #endif
Code Snippet Comments
0
William Hemsworth William Hemsworth is offline Offline | 29 Days Ago
•
•
•
•
Nice, neat, consistent format, and well commented code :]
 
 

Quick Comment
•
•
•
•
•
•
•
•
Message:
•
•
•
•


Similar Threads
Thread Tools Search this Thread



* adobe api append array arrays bash binarysearch centimeter char character cm copyanyfile copypdffile createcopyoffile createprocess() csyntax directory dynamic execv feet fgets file floatingpointvalidation fork frequency function getlogicaldrivestrin givemetehcodez global graphics gtkgcurlcompiling gtkwinlinux highest histogram homework i/o ide include infiniteloop initialization input interest intmain() iso keyboard kilometer license linked linkedlist linux linuxsegmentationfault list lowest match matrix meter microsoft mqqueue multi mysql oddnumber odf open openwebfoundation overwrite pdf pointer pointers posix power program programming pyramidusingturboccodes read recursion recv recvblocked repetition reversing scheduling segmentationfault send shape single socketprogramming stack standard strchr string strings suggestions test testautomation unix urboc user whythiscodecausesegmentationfault win32api windows.h
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC