public static void main(String[] args){
System.out.println("The largest prime factor of 600851475143 is "+largest(primeFactors(600851475143.0)));
}
public static ArrayList<Integer> factor(double n){
ArrayList<Integer> factors = new ArrayList<Integer>();
for(long i = 1; i<=n; i++){
if(isInt(n/i)){
factors.add((int)i);
}
}
return factors;
}
public static ArrayList<Integer> primeFactors(double n){
ArrayList<Integer> factors = factor(n);
ArrayList<Integer> primes = new ArrayList<Integer>();
for(int f : factors){
if(isPrime(f)){
primes.add(f);
}
}
return primes;
}
public static boolean isInt(double d){
return (d==(int)d);
}
public static boolean isPrime(double d){
return (factor(d).size()<=2);
}
public static long largest(ArrayList<Integer> integers){
int max = 1;
for(int i = 0; i<integers.size(); i++){
if(integers.get(i)>max){
max=integers.get(i);
}
}
return max;
}
Running this code causes my java to complain that it is out of memory? I wasn't expecting this to be a difficult problem to solve, as my code makes sense and works for smaller numbers, but it seems to have trouble with this one. Is there a problem in my code causing it to crash or is it simply that my code(or java in general) is not memory efficient? The largest number it could complete from subtracting numbers off of this larger one was "60085147.0" which it answered correctly. How can I get it to parse a larger number?
You have severe problems with integer overflows. isInt () will never return "true" if d ≥ 2^31. On the other hand, isPrime () will return "true" if d is twice a prime ≥ 2^31.
Out of curiousity, I'd love to know how long this code ran. It should be less than a millisecond, but I suspect your version took a bit longer. (Maybe I got your question wrong. Maybe you are not running out of memory, but out of time).
If you try other Project Euler problems: Do not try to solve the problems literally. You definitely don't need a list of all factors to find the largest prime factor of a number.