3

以下是我的代码，我尝试使用 BigInteger inn Java 计算从一到百的所有数字的 LCM。但它不提供任何答案。

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);
            }   
        }

}
4

2 回答 2

5

为什么不乘所有素数的最高幂直到 100。这是我在 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

答案是69720375229712477164533808935312303556800。

于 2016-09-10T15:28:08.977 回答
0

从 1 到 100 累积使用 LCM 会花费非常长的时间，即使它不会溢出BigInteger数据类型。尝试不同的算法。首先准备一个素数表 2,3,5,7,...,97，然后素数分解从 1 到 100 的每个数，并找出所有 100 个数中每个素数的最高幂。BigInteger最后，使用可能的类型来乘以素数的幂。答案是 2^6 * 3^4 * 5^2 * 7^2 * 从 11 到 97 的所有素数 = 69720375229712477164533808935312303556800。实际上，可以省去素数分解步骤。相反，人们只能找到每个素数在 100 以内的最高幂。BigInteger乘法无法避免，因为数字超过long long。

于 2016-09-10T15:32:46.027 回答