How to print prime factors of a number efficiently

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"


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.

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.