Java BigInteger Memory Optimization

I'm trying to find LCM of given N numbers. But this code of mine takes more than 32Mb memory. What kind of optimization can I perform here?

import java.util.Scanner ;
import java.math.BigInteger ; 
class Main {    
    public static BigInteger LCM( BigInteger a , BigInteger b ) {
        BigInteger c = a.gcd( b ) ;
        return a.multiply( b.divide( c ) ) ; 
    }
    public static void main( String[] args ) {
        Scanner s = new Scanner( System.in ) ;
        int n , t , ind , i ;    
        t = s.nextInt() ;
        for( ind = 1 ; ind <= t ; ind++ ) {
            n = s.nextInt() ;
            BigInteger res = BigInteger.ONE ;
            for( i = 0 ; i < n ; i++ ) {
                BigInteger a = s.nextBigInteger() ;
                res = LCM( res , a ) ;
            }
   开发者_如何学Go         System.out.println( "Case " + ind + ": " + res ) ;
        }
    }
}

Sample Input :

2
3
2 20 10
4
5 6 30 60

Sample Output :

Case 1: 20
Case 2: 60

---

Maybe you should try a good arbitrary precision math library like apfloat: http://www.apfloat.org/apfloat_java/ Another way is to implement an algorithm with lower space complexity. :)

Factorise all of them and multiply all prime factors with the greatest exponent. If all numbers are less than 10000, you can use primitives, and then do the multiplication with BigInt. This means far less objects to be created.

---

This program is not taking 32MB of anything. All of the classes of the JVM put together and their associated heap storage might be 32MB. Or, adding on the overhead of the JVM process, your OS might report it's using 32MB.

The most proximate answer is: you're not going to reduce this memory overhead by changing your program.

If you're running out of memory, well, give it more memory. java -Xmx1g lets the heap grow very large, to 1GB if it wants.

---

Use BigInteger.ONE, not new BigInteger("1"), but 32Mb isn't much really, practically any Java code takes that.

---

You can use java garbage collector to get accepted. Just call System.gc() after printing the solution for each case. Here is the modified code -

import java.util.Scanner ;
import java.math.BigInteger ; 
class Main {    
    public static BigInteger LCM( BigInteger a , BigInteger b ) {
        BigInteger c = a.gcd( b ) ;
        return a.multiply( b.divide( c ) ) ; 
    }
    public static void main( String[] args ) {
        Scanner s = new Scanner( System.in ) ;
        int n , t , ind , i ;    
        t = s.nextInt() ;
        for( ind = 1 ; ind <= t ; ind++ ) {
            n = s.nextInt() ;
            BigInteger res = BigInteger.ONE ;
            for( i = 0 ; i < n ; i++ ) {
                BigInteger a = s.nextBigInteger() ;
                res = LCM( res , a ) ;
            }
            System.out.println( "Case " + ind + ": " + res ) ;
            System.gc();
        }
    }
}

---

If you have to do this often then it might be a good idea to rethink the approach.

You might be able to statically create a data structure for factors of numbers 1 to 10000 and traverse it to quickly compute LCM of all numbers.

Its a guess but I think both your memory usage and speed should improve.