java - 如何确定极大的质因数？

Question

所以我试图在欧拉项目中找到问题 3 的答案。我需要确定给定数字的最大素因数。

引用欧拉项目:“13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？”

我已经构建了我的代码，它可以完美地处理任何 int 大小的东西。但由于他们给出的数字巨大，我的代码存在转换问题。

最初我尝试切换到长变量和长数组，但出现错误:'可能从 long 到 int 的有损转换'

那么我怎样才能让我的代码接受极长的数字呢？

public class Test {

long[] delers;

public static void main(String[] args) {
    Test test = new Test();
    test.determineDividers(600851475143,determineNumberOfDividers(600851475143));
    long a = test.determineHighestPrime(test.delers);
    System.out.println(a);
}

public void determineDividers(long getal,long aantalDelers) {
    delers= new long[aantalDelers];
    long k = 0;
    for (long i = 1; i < getal; i++) {
        if (getal % i == 0) {
            delers[k]=i;
            k++;                
        }
    }
}

public long determineNumberOfDividers(long getal) {
    int k = 0;
    for (long i = 1; i < getal; i++) {
        if (getal % i == 0) {
            k++;               
        }
    }
    return k;
}

public boolean determinePrime(long getal) {
    for (long i = 2; i < getal; i++) {
        if (getal % i == 0) {
            return false;
        }
    }
    return true;
}

public long determineHighestPrime(long[] deler) {
    for (long i = deler.length - 1; i > 0; i--) {
        if (determinePrime(deler[i]) == true) {
            return deler[i]);
        }
    }
    return 0;
}

}

感谢您的宝贵时间

编辑 1:添加来自 PE 的示例。

编辑2:添加解决方案

public class Test {

long[] delers;

public static void main(String[] args) {
    Test test = new Test();
    test.determineDividers(600851475143L,test.determineNumberOfDividers(600851475143L));
    long a = test.determineHighestPrime(test.delers);
    System.out.println(a);
}

public void determineDividers(long getal,int aantalDelers) {
    delers= new long[aantalDelers];
    int k = 0;
    for (long i = 1; i < getal; i++) {
        if (getal % i == 0) {
            System.out.println(i);
            delers[k]=i;
            k++;                
        }
    }
}

public int determineNumberOfDividers(long getal) {
    int k = 0;
    for (long i = 1; i < getal; i++) {
        if (getal % i == 0) {
            k++;               
        }
    }
    return k;
}

public boolean determinePrime(long getal) {
    for (long i = 2; i < getal; i++) {
        if (getal % i == 0) {
            return false;
        }
    }
    return true;
}

public long determineHighestPrime(long[] deler) {
    for (int i = deler.length - 1; i > 0; i--) {
        if (determinePrime(deler[i]) == true) {
            return deler[i];
        }
    }
    return 0;
}

}

Answer 1

当您设置数组时，数组的大小必须是int。因此，这个:

delers= new long[aantalDelers];

无法编译，因为您将参数aantalDelers声明为long。但是，当您调用 defineDividers 时，您为 aantalDelers 传入的值是 defineNumberOfDividers 的结果，您将其声明为返回 long ，但该函数表示返回 k，并且 k 是一个 int。

所以我认为你可以更改defineNumberOfDividers，使其返回int而不是long，并更改aantalDelers > 参数为 int 而不是 long。这样您就可以避免任何 long 到 int 的转换。另外，在使用 k 和 i 作为数组索引的地方，并将它们声明为 long，这些应该更改为 int 也。

我突然想到，我认为这会起作用，因为我认为 2⁶³ 以内的数字不能有超过 2³¹ 的除数。但是，如果我的数学错误并且可能是错误的，那么除了数组之外，您还需要一些其他机制。 (事实上​​，无论如何你可能需要想出另一种算法；我有一种感觉，这个算法将需要很长时间才能运行。)