java - 使用循环进行编程以实现数学目的。 ( java )

Question

让我解释一下这个问题。

我需要编写一个程序，在其中输入一个数字 N，然后我必须找到能被所有小数到 1 的数字整除的最小数字。

例如:。如果我的 N 是 5，那么答案就是 60。60 可以被 5、4、3、2 和 1 整除。

这是我到目前为止所拥有的......

import java.util.Scanner;

public class Questão_04 {
public static void main (String [] args)
{
    int x = 1, n = 1, d = x % n;

    System.out.print("Enter N: ");

    Scanner in = new Scanner(System.in);

    n = in.nextInt();

    do
    {
        if (d != 0)
        {
            x = x + 1;
            do
            {
                n = n -1;                   
            } while (n != 0);
        }
        else
        {
            do
            {
                n = n - 1;
            } while (d != 0);
        }

    } while (n != 0);

    System.out.print(x);\\the minimum number divisible by N and all up to N.

} 

Answer 1

用于查找该值的有效算法仅考虑小于或等于 N 的质数幂。

• 以 v = 1 开头
• 对于 p_i小于或等于 N 的素数
  • 查找最大整数 q_i这样p_i ^ q_i <= N
  • v *= p_i ^ q_i

对于您的示例 N=5，素数为 2,3,5 和

• 2^2 = 4 < 5 < 2^3
• 3^1 = 3 < 5 < 3^3
• 5^1 = 5 = 5 < 5^2

所以 v = 2^2 * 3 * 5 = 60

对于 N = 18，您最终会得到

v = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17

唯一棘手的一点是小于 N 的素数的生成。

然而，由于 v 随着 N 的增加而增长得非常快( O(N!) 或 O(N^log(N)) 或类似的东西)，在 N 的某个较低值(可能是数百个？)时，您将溢出整数(甚至长)算术意味着你可以通过预先计算一个小的素数表来逃脱惩罚。 (除非您使用任意精度数值类型)