How to find largest prime factor of 600851475143 in java

Question

I have some code that I am using for Project Euler. It is to find the largest prime factor of 600851475143. This is taking a really long time to run, at least 30 mins already. Can you guys see if it is just because my code takes too long, or my code is wrong. Also, any tips to make the run time faster?

public static void main(String[] args) {

        System.out.println(factor(600851475143L));


}
public static long factor(long rc){
    long num = rc;// need to add L to make it compile as long not int
    long i;
    long j;
    long largest = 0;
    long temp;

    for(i = 2; i<rc;i++){
        for(j=2;j<rc;j++){
            if(i%j==0){
                break;
            }
            if(j==rc-1){
                temp = i;
                if(largest<temp){
                    largest=temp;
                }
                else{
                    temp = 0;
                }
            }
        }

    }
    return largest;
}

@ScaryWombat it is to find all the prime numbers from 2-600851475143. — Justin Lin, Jun 29 '17 at 01:33
Take a look at https://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number. — user94559, Jun 29 '17 at 01:34
Consider finding all the NON-prime numbers between 1 and 6008... You can do this by marking all multiples of 2 as non-prime...then multiples of 3...and so on — Solace, Jun 29 '17 at 01:41

score 3 · Accepted Answer · answered Jun 29 '17 at 01:44

How about this solution:

public static long factor(long rc) {

   long n = rc;

   List<Long> pfactors = new ArrayList<Long>();

    for (long i = 2 ; i <= n ;  i++) {

        while (n % i == 0) {
            pfactors.add(i);

            n = n / i;

        }

    }

    return pfactors.get(pfactors.size() - 1);
}

Runs fast for me.

How to find largest prime factor of 600851475143 in java

1 Answers1