1

I need suggestions on how I can make this code runnable. For example, with this number: 600851475143. It works for smaller numbers. Any suggestions on my code overall would be more than welcome. As a side note, I understand it's Project Euler's policy not to share code to its problems, and thus I just want to be pushed in the right direction and don't want any direct answers. Thanks.

import java.util.List;
import java.util.ArrayList;
public class prime {

public static List<Long> factor2(long n){
    List<Long> list = new ArrayList<>();

    for (long a = 1; a < n; a++){
        for (long b = n; b>1; b--){
            if (a*b==n){
                list.add(a);
                list.add(b);
                a++;
                b--;
            }
            else{
                b--;
            }
        }

    }

    return list;
}
public static List<Long> prime (long n){
    List<Long>list = factor2(n);
    List<Long>listPrime = new ArrayList<>();
    for (long x : list){
        if (factor2(x).size()==2){
            listPrime.add(x);
        }
    }
    return listPrime;
}

public static long largestPrime (long n){
    long largest = 1;

    for (long x : prime(n)){
        if (x>largest){
            largest = x;
        }
    }
    return largest;
}

public static void main (String[] args){
    System.out.println(largestPrime(6));
}

}

Kaan
  • 5,434
  • 3
  • 19
  • 41
focusedchi
  • 11
  • 1
  • What is the output for that number as-is? – Michael Bianconi Jul 31 '19 at 17:37
  • do you mean what is it supposed to output? because right now the computational time is too great for it to compute – focusedchi Jul 31 '19 at 17:41
  • 1
    Oh, okay. So it's runnable, it's just too inefficient. – Michael Bianconi Jul 31 '19 at 17:46
  • With an _O(n²)_ runtime, this code is going to run a **very long time**, and will eventually cause **numeric overflow**, since `a = n - 1, b = n` will cause `a*b` to exceed the range of a `long`. Throw away that code and go look for a better algorithm online, if you truly want to find all divisors of large numbers, e.g. see [Efficiently getting all divisors of a given number](https://stackoverflow.com/q/26753839/5221149). – Andreas Jul 31 '19 at 17:53
  • I don't think this is really suitable for a SO question but I'd consider rethinking the solution. Having two for loops (that both loops through n times) is incredibly slow. Try to get it to 1 instead. An easy way to get there is by using division/modulo instead ;) Also, your code is getting all factors and prime, not only the largest prime. That could be a way to improve it, too. – ddmps Jul 31 '19 at 17:54
  • 2
    Suggest migration to https://codereview.stackexchange.com/ – mmking Jan 28 '20 at 18:32

0 Answers0