Posted By

binaryadder on 10/15/11


Tagged


Versions (?)

Problem 3


 / Published in: Java
 

Project Euler Question 3:

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

What is the largest prime factor of the number 600851475143?"

Output:

The largest prime factor of the number 600851475143 is 6857

  1. import java.math.*;
  2. import java.util.*;
  3.  
  4. public class Prob3{
  5. public static void main(String[] argsv){
  6. System.out.println("The largest prime factor of the number 600851475143 is " + greatestFac(primeFactors(600851475143l)));
  7. }
  8.  
  9. private static ArrayList<Long> primeFactors(Long n){
  10. ArrayList<Long> facs = new ArrayList<Long>();
  11. long prime = 2;
  12. while(((double)n/(double)prime) != 1.0){
  13. if(n % prime == 0){
  14. n = n / prime;
  15. facs.add(prime);
  16. }
  17. else prime = nextPrime(prime);
  18. }
  19. facs.add(prime);
  20. return facs;
  21. }
  22.  
  23. private static long greatestFac(ArrayList<Long> list){
  24. long high = list.get(0);
  25. for(int i = 1; i < list.size(); i++){
  26. if(list.get(i) > high) high = list.get(i);
  27. }
  28. return high;
  29. }
  30.  
  31.  
  32. // Find the next prime number after n (n + 1)
  33. private static long nextPrime(long n){
  34. n++; // remove if implementation details change (pass n + 1)
  35. while(!isPrime(n)){
  36. n++;
  37. }
  38. return n;
  39. }
  40.  
  41. private static boolean isPrime(long n){
  42. long limit = (long) Math.sqrt(n);
  43. for(long i = 2; i <= limit; i++){
  44. if(n % i == 0){
  45. return false;
  46. }
  47. }
  48. return true;
  49. }
  50.  
  51. } // end class Prob3

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: chauhanshiksha1 on October 7, 2012

3030829 too is a factor of 600851475143 and prime too.This should be the correct answser.Why it is not??

You need to login to post a comment.