Given a positive integer n
, your task is to find all its prime factors. Prime factors are the prime numbers that multiply together to give the original number.
For example, the prime factors of 60 are 2, 2, 3, and 5.
#include <stdio.h>
#include <math.h>
void primeFactors(int n) {
while (n % 2 == 0) {
printf("2 ");
n /= 2;
}
for (int i = 3; i <= (int)sqrt(n); i += 2) {
while (n % i == 0) {
printf("%d ", i);
n /= i;
}
}
if (n > 2) {
printf("%d", n);
}
printf("\n");
}
int main() {
int number = 60;
printf("Prime factors of %d are: ", number);
primeFactors(number);
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(log n) | If the number is a power of 2 (e.g., 2, 4, 8, 16...), we repeatedly divide by 2, which takes log₂(n) steps. |
Average Case | O(√n) | We check for divisibility from 2 up to √n. Each time we divide out a factor completely before continuing, which ensures no repeated work. This is efficient for most values of n. |
Worst Case | O(√n) | In the worst case (e.g., when n is a large prime), we must try all numbers up to √n to determine that it has no smaller prime factor. |
Comments
Loading comments...