C Program for Find largest prime factor of a number
Given a positive integer ‘n'( 1 <= n <= 1015). Find the largest prime factor of a number.
Input: 6 Output: 3 Explanation Prime factor of 6 are- 2, 3 Largest of them is '3' Input: 15 Output: 5
Method 1:
The approach is simple, just factorise the given number by dividing it with the divisor of a number and keep updating the maximum prime factor. See this to understand more.
c
// C Program to find largest prime // factor of number #include <math.h> // A function to find largest prime factor long long maxPrimeFactors( long long n) { // Initialize the maximum prime factor // variable with the lowest one long long maxPrime = -1; // Print the number of 2s that divide n while (n % 2 == 0) { maxPrime = 2; n >>= 1; // equivalent to n /= 2 } // n must be odd at this point, thus skip // the even numbers and iterate only for // odd integers for ( int i = 3; i * i <= n; i += 2) { while (n % i == 0) { maxPrime = i; n = n / i; } } // This condition is to handle the case // when n is a prime number greater than 2 if (n > 2) maxPrime = n; return maxPrime; } // Driver program to test above function int main() { long long n = 15; printf ( "%lld\n" , maxPrimeFactors(n)); n = 25698751364526; printf ( "%lld" , maxPrimeFactors(n)); return 0; } // This code is modified by Susobhan Akhuli |
Output:
5 328513
Time complexity:
Auxiliary space:
Method 2:
Follow the steps below for the implementation:
- Initialize variables largest_prime to -1, i to 2, and n to the input integer.
- Start a while loop that continues as long as i * i <= n. This loop will iterate through all possible factors of n.
- In the while loop, start another while loop that continues as long as n % i == 0. This inner loop will divide n by i until n is no longer divisible by i.
- In the inner loop, set largest_prime to i, and update n by dividing it by i.
- At the end of the inner loop, increment i by 1.
- After the outer loop, if n > 1, set largest_prime to n. This is because n could be a prime number larger than any of its factors.
- Return largest_prime.
Below is the implementation of the above approach:
C
// C code to find largest prime factor of number #include <stdio.h> // Function to find the largest prime factor of a positive // integer 'n' long long maxPrimeFactors( long long n) { long long largest_prime = -1, i = 2; while (i * i <= n) { while (n % i == 0) { largest_prime = i; n = n / i; } i = i + 1; } if (n > 1) { largest_prime = n; } return largest_prime; } int main() { long long n = 15; printf ( "%lld\n" , maxPrimeFactors(n)); n = 25698751364526; printf ( "%lld\n" , maxPrimeFactors(n)); return 0; } // This code is contributed by Susobhan Akhuli |
Output
5 328513
Time complexity: O(sqrt(n)).
Auxiliary space: O(1)
Please refer complete article on Find largest prime factor of a number for more details!
Contact Us