Java中的素数 - 算法

Question

我已经开始学习使用Java编写代码并决定使用Project Euler站点给我一些小任务来尝试完成我学习的每一段新编码.所以我遇到了问题3:

13195的主要因素是5,7,13和29. 600851475143中最大的素数是多少？

我考虑了这个问题并研究了很多关于素数的不同理论以及如何通过各种不同的计算找到它们(以Eratosthenes的筛子为例)我想出的解决方案是测试2 - > n中的数字并查看是否它们是素数,如果它们是那么我将Tn变量(在这种情况下为600851475143)除以新发现的素数并查看它是否是一个因子.如果是,我会将它分配给变量Hp(最高素数),在程序结束时我会将Hp输出到控制台给出我的结果.

这是我的代码:

public class Largest_Prime_Factor_NEW_SOLUTION {

    static long Tn = 600851475143L;
    static long Hp = 0;
    static boolean isPrime = false;

    public static void main(String[] args) {

        for (long i=2; i<Tn; i++) {
            System.out.println("TESTING NUMBER " + i);
            for (long k=2; k < i; k++) {
                if (i % k == 0) {
                    System.out.println(i + " IS NOT A PRIME");
                    break;
                } else if (k + 1 == i) {
                    isPrime = true;
                }
            }

            if (isPrime) {
            System.out.println(i + " IS A PRIME");
            if (Tn % i == 0) {
                System.out.println(Tn + " IS DIVISIBLE BY " + i);
                Hp = i;
            } else {
                System.out.println(Tn + " IS NOT DIVISIBLE BY " + i);
            }
            }

            isPrime = false;
        }
        System.out.println("THE HIGHEST PRIME NUMBER OF " + Tn + " IS " + Hp);
    }
}

现在我知道这段代码非常低效,刚开始我已经设法从我开始的地方压缩它(到处都有循环!)但我要问的是,我该如何改进呢？它正在吞噬我,因为我所研究的一切都与别人会做的事情相矛盾,这让人非常困惑.我已经尝试了筛选方法,但我知道布尔数组只能是一个int数组,而不是一个长数组？

我明白,在开始编码时,我将仅限于我可以使用的知识,但仅仅是出于兴趣,我很想知道最终的解决方案是什么.

Answer 1

你能做的就是找到最低的除数Tn.假设是p,再次找到最低的除数Tn/p,依此类推.

现在,每一步p都是素数[下面的解释].所以收集他们,他们是主要的除数Tn.

为了获得更好的时间复杂度,您可以检查最多ceil(sqrt(Tn))只有除数的除数,而不是Tn-1.

当你开始检查主要除数时Tn,你可以从开始2.一旦你得到一个素因子,p不会再次启动2了Tn/p.因为,Tn/p同样的除数Tn,自Tn不必因数小于p,Tn/p不具备这一点.所以p再次开始[ p可以有多个电源Tn].如果p不分Tn,请转到p+1.

示例:

Tn = 45
1.从2开始.2不除45.
2.下一个测试用于3. 45可被3整除.因此3是它的主要除数.
3.现在检查45/3 = 15的素数除数,但从3开始,而不是从2开始.4.好吧,15可以被3整除.所以从15/3 = 5开始5.注意5,ceil(sqrt(5))是3.但是5不能被3整除.但是因为4> ceil(sqrt( 5))我们可以毫无疑问地说5是素数.

所以45的主要除数是3和5.

为什么一个数字的最小除数(1除外)是素数？

假设上述陈述是错误的.然后数字N具有最小但复合除数,比如说C.

所以C | N现在C是复合的,它的除数小于自身但大于1.
假设C的这个除数是P.
So P | C,但我们有C | N => P | N其中1 <P <C

这与我们的假设相矛盾,即C是N的最小除数,因此数字的最小除数总是素数.