An Efficient Algorithm to Find All the Prime Factors of a Number | Algorithms

An Efficient Algorithm to Find All the Prime Factors of a Number | Algorithms

Most Efficient Algorithm to Find All the Prime Factors of a Number thecsengineer Saumya Ranjan Nayak


The Objective :

To find all the prime factors of a number most efficiently .

Let's assume the number of which we have to find all the factors is n.

Naive Approach :

So, basically what we have to do is that we have to find all such prime numbers that divide n completely or are factors of n.

So , at first the what strikes our mind is that we would just iterate from 2 to the square root of n, which basically is the whole set of numbers from which some may be the factors of n and then check if that number is prime and if it is then check whether it divides n and if it does we store it as a prime factor of the number n .


Efficient Approach :
Note : Let's keep in mind that every prime number is odd except 2 .
So, the steps that we can follow to optimize the algorithm is that :

 ✔️ First we make a while loop and check whether n is divisible by it and if it does then just keep dividing it until it isn't divisible any more or it becomes one , exactly like how we simply factorize by hand .
                              Most Efficient Algorithm to Find All the Prime Factors of a Number thecsengineer Saumya Ranjan Nayak

✔️ So, now we have already tested the number against the only even prime number 2. Now we know that all the prime numbers are odd so instead of traversing all the way upto the square root, we can just start from 3 which the next prime number and keep incrementing it by 2 (i=i+2) in every iteration so that we keep ending up with just odd numbers in every iteration  .So by just using this simple trick we just cut around half of the operation that would have happened if we would have taken all the even numbers into account as we had thought in our naive approach.

✔️ So by following the above steps we get store all the prime factors and at last our number n would be reduced to 1 due to all the divisions with its factors throughout the process , provided if the number is not prime . But if the number is prime no one would be able to divide it and so it itself is it's own prime factor . So , at last we can just perform a check that if n is greater than 1 then we store the n itself as the prime factor .

Enough of the talks lets now see it's implementation :


Taken from the Competitive Programming Repository Do give a star ! ๐ŸŒŸ 

Thanks, Keep Learning ๐Ÿงก

Do share your thoughts in the comments .
...

Saumya Ranjan Nayak


๐Ÿ‘ˆ Do Share ๐Ÿ‘‹