Results 1 to 8 of 8
Thread: Finding Largest Prime Factor
 03212008, 07:36 PM #1Member
 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 ?
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; } 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); } }
anyone have any alternative code or any idea to get the right answer?
 03242008, 06:33 AM #2Java 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 == i1) { 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); } }
 03262008, 07:04 AM #3Member
 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.
 10162008, 02:37 AM #4Member
 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); 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 ; }
 10162008, 06:10 AM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 21
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.
 11082010, 07:41 PM #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.
 11082010, 08:18 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,051
 Blog Entries
 7
 Rep Power
 23

This thread is over 2 yrs old. Locking.
Similar Threads

Computing prime numbers in Java
By Java Tip in forum java.langReplies: 0Last Post: 04122008, 08:39 PM 
Prime numbers
By gapper in forum New To JavaReplies: 3Last Post: 02072008, 11:09 AM 
Finding largest and smallest integer
By mlhazan in forum New To JavaReplies: 2Last Post: 01122008, 11:30 PM 
ArrayList problem (finding largest no)
By bugger in forum New To JavaReplies: 3Last Post: 12122007, 01:47 PM 
Finding largest no
By bugger in forum New To JavaReplies: 11Last Post: 11292007, 01:49 PM
Bookmarks