Home > Programming > What is the largest prime factor of the number 600851475143 ?

What is the largest prime factor of the number 600851475143 ?


The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Here is the Java code using BigInteger to represent the given number.

package projecteuler;
import java.math.BigInteger;
/**
*
* @author Vasanth Raja Chittampally
*/
public class ProjectEuler {
public static void main(String[] args)
{
BigInteger bi=new BigInteger("600851475143");
int div=7;
while(bi.compareTo(new BigInteger("1"))!=0) {
while(bi.mod(new BigInteger(div+"")).compareTo(new BigInteger("0"))==0) {
bi=bi.divide(new BigInteger(div+""));
}
div+=2;
}
System.out.println(""+div);
}
}

I tested the above code using Java. The answer it gives is 6857. It does take less than 1sec of execution time.

  1. Thomas Leslie
    October 4, 2011 at 4:50 pm

    Hy!

    Thanks the nice solution! Can you tell me which Primality test did you use? I tried many of them, but my applications were too slow!

  2. Manithda
    February 26, 2013 at 3:02 am

    I copy your code but my answer is 6859. why?

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: