Problem #3 on Project Euler is:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
My solution takes forever. I think I got the right implementation; however, when testing with the big number, I have not being able to see the results. It runs forever. I wonder if there's something wrong with my algorithm:
public class LargestPrimeFactor3 {
public static void main(String[] args) {
long start, end, totalTime;
long num = 600851475143L;
long pFactor = 0;
start = System.currentTimeMillis();
for(int i = 2; i < num; i++) {
if(isPrime(i)) {
if(num % i == 0) {
pFactor = i;
}
}
}
end = System.currentTimeMillis();
totalTime = end - start;
System.out.println(pFactor + " Time: "+totalTime);
}
static boolean isPrime(long n) {
for(int i = 2; i < n; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
}
Although not in Java, I think you can probably make out the following. Basically, cutting down on the iterations by only testing odd divisors and up to the square root of a number is needed. Here is a brute force approach that gives an instant result in C#.
static bool OddIsPrime (long oddvalue) // test an odd >= 3
{
// Only test odd divisors.
for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
static void Main(string[] args)
{
long max = 600851475143; // an odd value
long maxFactor = 0;
// Only test odd divisors of MAX. Limit search to Square Root of MAX.
for (long i = 3; i <= Math.Sqrt(max); i += 2)
{
if (max % i == 0)
{
if (OddIsPrime(i)) // i is odd
{
maxFactor = i;
}
}
}
Console.WriteLine(maxFactor.ToString());
Console.ReadLine();
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With