# Yaroslav Prozorov # How to print prime factors of a number efficiently

"In a realm where numbers hold secrets, a captivating challenge awaits, which is to Find all the Prime factors of a Number"

## Description

Problem: We are given a number n. The task is to print all prime factors of n.

Prime Factors: They are prime numbers, which are factors of a given number.

Example:
Input: `12`

Output: `2 2 3`

### Naive Approach

Iterate from `2 to (n-1)` and if the number is prime. If the number is prime, then divide the given number by this number, till it remains completely divisible.

Time Complexity: `O(nlogn)` ### Efficient Approach

Iterate all numbers `from 2 to the square root of n` and for every check if it divides n. Repetitively divide n by the number till it remains completely divisible and print the values.

Time Complexity: `O(sqrt(n))` However, if you have a big number, how could you reduce the steps? Look at the below.

### More Efficient Approuch

The first step is to check our number is divisible by `2` or `3`. If yes, make a loop. It means we can skip numbers `2,3,4,6,8,10,12...` and so on, which reduces the steps.
The second step is to check from 5 and we will not increment by 1. We will do it by 6. And inside the for-loop, we have two while loops and one check `i + 2` that the same idea reduces the steps. ### In conclusion

Thanks for your time and have a nice day, I wish you lack in solving a problem.