09. Largest Prime Factor

The problem can be found at the following link: Question Link

My Approach

To find the largest prime factor of a given number n,

• I iterate from 2 up to the square root of n.

  • During this iteration, I repeatedly divide n by i as long as n is divisible by i, and keep track of the largest factor encountered.

• Finally, I return the largest factor, which is also the largest prime factor of n.

Time and Auxiliary Space Complexity

• Time Complexity: The loop runs from 2 to the square root of n, which results in a time complexity of O(sqrt(n)).

• Auxiliary Space Complexity: O(1) as I am using a constant amount of extra space to store the result.

Code (C++)

class Solution {
public:
    long long int largestPrimeFactor(int n) {
        int out = 2;
        int checkUpto = sqrt(n);
        for (int i = 2; i <= checkUpto; ++i) {
            while (n % i == 0) {
                n = n / i;
                out = max(out, i);
            }
        }
        out = max(out, n);
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.