如何确定极大的质因数？

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

将所有将得到“巨人”的变量更改为BigInteger。您需要更新数学以使用函数调用而不是java操作数，但它们都可以在BigInteger中使用。

Answer 2

设置数组时，数组的大小必须是int。因此，这：

delers= new long[aantalDelers];

无法编译，因为您已将参数a antaldelers声明为long。但是，当您调用确定标识符（determineDividers）时，为确定标识符（antaldelers）传入的值是确定标识符（determinediumberofdividers）的结果，您声明该值返回长，但该函数表示返回k，而k是int。

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

恕我直言，我认为这是可行的，因为我认为一个2^{63的数字不能有超过231的除数。但是，如果我的数学是错误的，并且它可以，那么除了数组之外，您还需要其他一些机制。（事实上，无论如何，您可能需要想出另一个算法；我感觉这个算法需要很长时间才能运行。）}