CODEWITHSUNDEEP
javamathnumbersprimesprime-factoring
mendokusai
mendokusai

Reputation: 185

More efficient way of finding the largest prime factor of the number 600851475143

I tried to find the largest prime factor of the number 600851475143 and succeeded with the code below but I know this is a brutal force way and there is probably more efficient and elegant way of solving this problem. However, I couldn't think of any immediately and was hoping if someone can share their solutions with explanation. 

public class Solution {

    // find prime numbers
    ArrayList<Long> primelist = new ArrayList<>();

    ArrayList<Long> findPrime(Long num) {
        for (Long i = Long.valueOf(2); i <= num; i++) {
            if (num % i == 0) {
                primelist.add(i);
                num = num / i;
                if (num == 1) {
                    break;
                }
            }
        }
        System.out.println(primelist);
        return primelist;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.findPrime(Long.valueOf(600851475143L)); // [71, 839, 1471, 6857]
    }
}

Upvotes: 1

Views: 618

Answers (1)

Stephen C
Stephen C

Reputation: 719739

If the number that you are trying to factorize is a product of two large prime numbers, then factorization is computationally expensive. However, your algorithm is (as you observe) is particularly inefficient.

Here are couple of simple ways to speed up your program:

  1. Don't use Long for your computations. Use long instead. Your code will be generating and garbage collecting large numbers of Long objects.

  2. When using trial division to factorize a number n, you can stop looking for prime factors when you get to sqrt(n).

  3. When you find a prime factor, you can speed up the factorization by dividing the original number by the factor, then trying to factorize the result. (In fact, you are already doing this.)

(But this is "chicken feed" compared to more sophisticated algorithms.)

Upvotes: 2

Related Questions