Finding Largest Prime Factor

[perito]

Im trying to solve this problem

Quote:

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:

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;
			}
			i=i.add(BigInteger.ONE);
		}
		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);
		BigInteger answer=BigInteger.ZERO;
			while(i.compareTo(BigInteger.ONE)>0)
			{
				if (num.mod(i).equals(BigInteger.ZERO) && isPrime(i)==true)
					{
						answer=i;
						break;
					}
				i=i.subtract(BigInteger.ONE);
			}
		System.out.println(answer);
	}
}

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?

[hardwired]

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]);
                factors.add(Long.valueOf(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);
    }
}

[blackhole8746]

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.

[eNine]

here are two methods from a class that I wrote...these might be helpful. you'd still need to do a little work...

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);
	listOfPrimes.add(2L);//add two

//only add odd numbers
for(long  potentialPrime = 3;potentialPrime<= upToWhat; potentialPrime+=2){
		if(isPrime(potentialPrime))
			listOfPrimes.add(potentialPrime);
	}
	return listOfPrimes ;
}

[Eranga]

Quote:

Originally Posted by perito

I waited about an hour and got no results...

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.