C Programming: Find all prime factors of a given integer

Last update on December 20 2024 13:06:43 (UTC/GMT +8 hours)

Write a C program that accepts an integer and find all prime factors of the integer.

Prime factors of a number are those factors that are prime numbers. 2 and 4 are factors of 4, where 2 is considered the prime factor.

Test Data:
(77) -> 7, 11
(12) -> 2, 2, 3
(45) -> 3, 3, 5

Sample Solution:

C Code:

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

int main(void) {
  int n;
  printf("Input an integer: ");
  scanf("%d", &n); // Accepting an integer input

  if (n > 0) { // Checking if the input is a positive number
    // Dividing the number by 2 until it's odd and printing the factors of 2
    while (n % 2 == 0) { 
      printf("2 "); 
      n /= 2; 
    }   
    // Loop to find and print factors starting from 3 up to the square root of 'n'
    for (int i = 3; i <= sqrt(n); i += 2) { // Incrementing by 2 as even numbers are already factored by 2
      while (n % i == 0) { // Check if 'i' is a factor of 'n'
        printf("%d ", i); // Print the factor 'i'
        n /= i; // Update 'n' by dividing with the factor 'i'
      } 
    } 
    if (n > 2) 
      printf("%d", n); // If 'n' is greater than 2 and not fully factored, print it
  }
}

Sample Output:

Input an integer: 78
2 3 13

Flowchart:

C Programming Code Editor:

Click to Open Editor

Improve this sample solution and post your code through Disqus.

Previous: K^th smallest number in a multiplication table.
Next: Count common factors of two integers.