C Program to Perform the Unique Factorization of a Given Number

«
»
This is a C Program to get all the unique factors of a given integer such that addition of a partition results an integer. Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers.

Here is source code of the C Program to Perform the Unique Factorization of a Given Number. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. void printarray(int p[], int n) {
  3.     int i;
  4.     for (i = 0; i < n; i++)
  5.         printf("%d ", p[i]);
  6.     printf("\n");
  7. }
  8. void partition(int n) {
  9.     int p[n]; // An array to store a partition
  10.     int k = 0; // Index of last element in a partition
  11.     p[k] = n; // Initialize first partition as number itself
  12.     int rem_val;
  13.     // This loop first prints current partition, then generates next
  14.     // partition. The loop stops when the current partition has all 1s
  15.     while (1) {
  16.         // print current partition
  17.         printarray(p, k + 1);
  18.         rem_val = 0;
  19.         while (k >= 0 && p[k] == 1) {
  20.             rem_val += p[k];
  21.             k--;
  22.         }
  23.         // if k < 0, all the values are 1 so there are no more partitions
  24.         if (k < 0)
  25.             return;
  26.         // Decrease the p[k] found above and adjust the rem_val
  27.         p[k]--;
  28.         rem_val++;
  29.         // If rem_val is more, then the sorted order is violated.  Divide
  30.         // rem_val in different values of size p[k] and copy these values at
  31.         // different positions after p[k]
  32.         while (rem_val > p[k]) {
  33.             p[k + 1] = p[k];
  34.             rem_val = rem_val - p[k];
  35.             k++;
  36.         }
  37.         // Copy rem_val to next position and increment position
  38.         p[k + 1] = rem_val;
  39.         k++;
  40.     }
  41. }
  42. int main() {
  43.     int num;
  44.     printf("\nEnter a number to perform integer partition: ");
  45.     scanf("%d", &num);
  46.     partition(num);
  47.     return 0;
  48. }

Output:

advertisement
$ gcc UniqueFactors.c
$ ./a.out
 
 
Enter a number to perform integer partition: 4 
4
3 1 
2 2 
2 1 1 
1 1 1 1

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter