"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.