The problem is this: Find the largest prime factor of a given number. One brute force way is to find a factor of the given number and then perform primality testing on the number. But the test to check if the number is prime or not is a costly operation if one does not have a set of all primes.
So there was a need for me to avoid the testing of a number for primality.
One interesting thing to be noticed is that the smallest factor of a number has to be prime. Suppose if it were not, then it implies that it can be written as a product of two smaller numbers which contradicts the hypothesis that the factor is the smallest factor.
So we can avoid the testing of primality by taking the smallest factor. But the problem requires us to determine the largest prime factor. The lergest prime factor can be recursively obtained by using the following:
public static long largestPrimeFactor(long n) {
long prime = smallestPrimeFactor(n);
return Math.max(prime, largestPrimeFactor(n/prime));
}
Where the smallest prime factor method returns the smallest factor of n.
One of the interesting things that I read while solving this problem was that after 3, all the prime numbers satisfy the general formula 6n-1, 6n+1. So the primes will be in the series :
6(1) – 1 = 5
6(1) + 1 = 7
6(2) – 1 = 11
6(2) + 1 = 13 …
In fact, primes after the number p belong to the series p# n + m, where p# is called the primorial. Look up the wiki entry to learn more.
Popularity: 4% [?]
Related posts:
