NYOJ 517 最小公倍数（1-n 个数的最小公倍数，大数）

╰+哭是因爲堅強的太久メ 2022-09-17 13:23 159阅读 0赞

[http://acm.nyist.net/JudgeOnline/problem.php?pid=517][http_acm.nyist.net_JudgeOnline_problem.php_pid_517]

/*
     为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。 但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。 事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
    
     我们希望寻找到能除尽1至n的的每个数字的最小整数。
    
     不要小看这个数字，它可能十分大，比如n=100, 则该数为： 69720375229712477164533808935312303556800
    
     请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。
    
     例如： 用户输入： 6 程序输出： 60
    
     用户输入： 10 程序输出： 2520
    
     要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。 相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性； 不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。
    
    
    
     本题满分：19分
    
     共4个用例：
    
     (2分) 输入： 3 输出： 6
    
     (3分) 输入： 16 输出： 720720
    
     (5分) 输入： 25 输出： 26771144400
    
     (9分) 输入： 77 输出： 410555180440430163438262940577600
    
    
     最小公倍数就是所有质数的相应幂的积
     比如N=10
     小于10的质数有2,3,5,7
     对应的最大幂是：3，2，1，1
     则最小公倍数是：2^3x3^2x5^1x7^1 = 2520
    
     * 
     */
    
    import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Minmugcd {
    	static boolean issushu(int n) {
    		if (n == 2 || n == 1)
    			return true;
    		for (int i = 2; i <= Math.sqrt(n); i++) {
    			if (n % i == 0)
    				return false;
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    		BigInteger ans;
    		int tmp = 0;
    		Scanner cin = new Scanner(System.in);
    		while (cin.hasNext()) {
    
    			ans = BigInteger.ONE;
    			int n = cin.nextInt();
    			// System.out.println("n="+n);
    			for (int i = 2; i <= n; i++) {
    				tmp = 1;
    				if (issushu(i)) {
    					while (tmp * i <= n) {
    						tmp *= i;
    					}
    				}
    				// System.out.println(tmp);
    				ans = ans.multiply(BigInteger.valueOf(tmp));
    			}
    			System.out.println(ans);
    
    		}
    	}
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_517]: http://acm.nyist.net/JudgeOnline/problem.php?pid=517