Results 1 to 8 of 8
Thread: Finding Largest Prime Factor
- 03-21-2008, 06:36 PM #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 ?
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?
- 03-24-2008, 05: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 == 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); } }
- 03-26-2008, 06:04 AM #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.
- 10-16-2008, 02:37 AM #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); 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 ; }
- 10-16-2008, 06:10 AM #5
- Join Date
- Jul 2007
- Location
- Colombo, Sri Lanka
- Posts
- 11,370
- Blog Entries
- 1
- Rep Power
- 26
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.
- 11-08-2010, 06: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.
- 11-08-2010, 07:18 PM #7
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
-
This thread is over 2 yrs old. Locking.
Similar Threads
-
Computing prime numbers in Java
By Java Tip in forum java.langReplies: 0Last Post: 04-12-2008, 08:39 PM -
Prime numbers
By gapper in forum New To JavaReplies: 3Last Post: 02-07-2008, 10:09 AM -
Finding largest and smallest integer
By mlhazan in forum New To JavaReplies: 2Last Post: 01-12-2008, 10:30 PM -
ArrayList problem (finding largest no)
By bugger in forum New To JavaReplies: 3Last Post: 12-12-2007, 12:47 PM -
Finding largest no
By bugger in forum New To JavaReplies: 11Last Post: 11-29-2007, 12:49 PM
Bookmarks