# Thread: Finding Largest Prime Factor

1. Member
Join Date
Feb 2008
Posts
9
Rep Power
0

## Finding Largest Prime Factor

Im trying to solve this problem
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
My code is this:
Java Code:
```import java.math.BigInteger;
public class LargestPrimeFactor
{
public static boolean isPrime(BigInteger nbr)
{
boolean isNPrime=true;
BigInteger i = BigInteger.valueOf(2);
while (i.compareTo(nbr.divide(BigInteger.valueOf(2))) < 0)
{
if ((nbr.compareTo(i) != 0) && (nbr.mod(i).equals(BigInteger.ZERO)))
{
isNPrime = false;
break;
}
}
if (isNPrime == true) return true;
else return false;
}
public static void main(String[] args)
{
String strNum = "600851475143";
BigInteger num = BigInteger.valueOf(Long.parseLong(strNum));
BigInteger i = BigInteger.valueOf(Long.parseLong(strNum)-1);
while(i.compareTo(BigInteger.ONE)>0)
{
if (num.mod(i).equals(BigInteger.ZERO) && isPrime(i)==true)
{
break;
}
i=i.subtract(BigInteger.ONE);
}
}
}```
I think this code will work but it will take FOREVER to work, I waited about an hour and got no results...
anyone have any alternative code or any idea to get the right answer?

2. Java Code:
```import java.util.*;

public class FindingPrimes {

public static void main(String[] args) {
System.out.printf("int max value  = %d%n" +
"long max value = %d%n" +
"given value    = %d%n",
Integer.MAX_VALUE, Long.MAX_VALUE,
600851475143L);
System.out.println();

// Generate and store the first 1000 prime numbers.
boolean print = false;
long[] primes = new long[1000];
int count = 1;
int index = 0;
if(print)
System.out.printf(" %5d, ", 2);
primes[index++] = 2;
for(int i = 1; i < 7920; i++) {
for(int j = 2; j < i; j++) {
if(i % j == 0)
break;
if(j == i-1) {
primes[index++] = i;
if(print) {
System.out.printf(" %5d, ", i);
if(++count > 9) {
count = 0;
System.out.println();
}
}
}
}
}

// Try to factor the given value with these primes.
long value = 600851475143L;
System.out.println("------ factor " + value + " ------");
List<Long> factors = new ArrayList<Long>();
for(int i = 0; i < primes.length; i++) {
if(value % primes[i] == 0) {
System.out.printf("primes[%3d] = %4d%n",
i, primes[i]);
}
}
System.out.printf("%s%n", factors);
long product = 1;
for(int i = 0; i < factors.size(); i++) {
product *= factors.get(i).longValue();
}
System.out.printf("product = %d%n", product);
}
}```

3. Member
Join Date
Mar 2008
Posts
2
Rep Power
0
You seriously waited for an hour?!! I'm a beginner too but if you wait that long do two things:

1- Check your output statements (And no I don't think you're stupid, we all make that one silly mistake)
2- Check your while loops. If any while loop is infinite, or you forgot to increment one of the variables you're using in the loop body the program will not run.

4. Member
Join Date
Aug 2007
Location
new yrok
Posts
3
Rep Power
0
here are two methods from a class that I wrote...these might be helpful. you'd still need to do a little work...

Java Code:
```public boolean isPrime(long p){

long pAsALong = p;
long mySqrt = (long)Math.sqrt(pAsALong );
long divisor = 3;
if(p%2 == 2)
return true;
else if(p%2 == 0)
return false;

while(divisor <= mySqrt )
{

if(pAsALong % divisor == 0)
return false;

//only check odd numbers
divisor+=2;
}

return true;
}

//@return array list of longs that are prime factors
public ArrayList<Long> listPrimes(long upToWhat){
ArrayList<Long> listOfPrimes = new ArrayList<Long>(20);

for(long  potentialPrime = 3;potentialPrime<= upToWhat; potentialPrime+=2){
if(isPrime(potentialPrime))
}
return listOfPrimes ;
}```

5. Originally Posted by perito
Amazing, why are you stay that much time for a result. If your application take an hour to give an output how can it become useful at all. Best thing to do in such a case is debug the code and see where you hang on. Specially on loops those things can be happen.

Check hardwireds' code. All what you want is there.

6. You don't have to use a long integer!
Just do that:
long number = 600851475143L;
The L at the end shows, that the variable is of type long.

7. Originally Posted by perito
What is the largest prime factor of the number 600851475143 ?
6857

kind regards,

Jos

ps. the other prime factors are 1471, 839 and 71

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•