CODEWITHSUNDEEP
javabigintegerlcm
kulst
kulst

Reputation: 144

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 100?

Following is my code where I tried to calculate LCM of all numbers from one to hundred by using BigInteger inn Java. But it does not provide any ans.

import java.math.BigInteger;

public class CommonOneToHundred {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BigInteger res =new BigInteger("1");
        int i = 2;
        while(i<=100){
        res = lcm(res,BigInteger.valueOf(i));
        i++;
        }
        System.out.println(res);
    }
       static BigInteger lcm(BigInteger x, BigInteger y)
        {
            BigInteger a;
            //a = (x > y) ? x : y; // a is greater number
            a = y;
            while(true)
            {
                if(a.divide(x).equals(0) &&  a.divide(y).equals(0))
                    return a;
                a = a.add(BigInteger.ONE);
            }   
        }

}

Upvotes: 3

Views: 930

Answers (2)

Zhuoran He
Zhuoran He

Reputation: 983

Using LCM accumulatively from 1 to 100 is going to take extremely long time, even if it does not overflow the BigInteger data type. Try a different algorithm. First prepare a prime table 2,3,5,7,...,97, then prime factorize every number from 1 to 100 and find the highest power of every prime in all 100 numbers. Finally, multiply those powers of prime factors using probably the BigInteger type. The answer is 2^6 * 3^4 * 5^2 * 7^2 * all primes from 11 to 97 = 69720375229712477164533808935312303556800. In fact, the prime factorization step can be saved. One can just find the highest power of each prime that is within 100 instead. The BigInteger multiplication cannot be avoided, since the number exceeds long long.

Upvotes: 0

advocateofnone
advocateofnone

Reputation: 2541

Why not take multiplication of highest power's of all primes till 100. Here is my code in python. 

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
ans = 1
for prime in primes:
  power = 0
  tmp = 1
  while tmp <= 100:
    tmp = tmp*prime
    power += 1
  ans = ans * prime**(power-1)

print ans

The answer is 69720375229712477164533808935312303556800.

Upvotes: 5

Related Questions