Java中的Prime分解程序

Question

我正在研究用Java实现的素数分解程序.目标是找到最大的素数因子600851475143(项目欧拉问题3).我想我已经完成了大部分工作,但是我遇到了一些错误.此外,我的逻辑似乎已关闭,特别是我设置的方法,用于检查数字是否为素数.

public class PrimeFactor {

    public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i < Math.sqrt(600851475143L); i++) {
            if (Prime(i) && i % Math.sqrt(600851475143L) == 0) {
                count = i;
                System.out.println(count);
            }
        }
    }

    public static boolean Prime(int n) {
        boolean isPrime = false;
        // A number is prime iff it is divisible by 1 and itself only
        if (n % n == 0 && n % 1 == 0) {
            isPrime = true;
        }
        return isPrime;
    }
}

编辑

public class PrimeFactor {

    public static void main(String[] args) {
        for (int i = 2; i <= 600851475143L; i++) {
            if (isPrime(i) == true) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int number) {
        if (number == 1) return false;
        if (number == 2) return true;
        if (number % 2 == 0) return false;
        for (int i = 3; i <= number; i++) {
            if (number % i == 0) return false;
        }
        return true;
    }
}

Answer 1

为什么要这么复杂？你不需要像isPrime()那样做任何事情.除以它的最小除数(素数)并从这个素数做循环.这是我的简单代码:

public class PrimeFactor {

    public static int largestPrimeFactor(long number) {
        int i;

        for (i = 2; i <= number; i++) {
            if (number % i == 0) {
                number /= i;
                i--;
            }
        }

        return i;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(largestPrimeFactor(13195));
        System.out.println(largestPrimeFactor(600851475143L));
    }
}

Answer 2

编辑:我希望这听起来不是一个令人难以置信的居高临下的答案.我只是想说明一下,从计算机的角度来看,你必须检查所有可能是X因子的数字,以确保它是最佳的.计算机只是通过查看就不知道它是复合的,所以你必须迭代

示例:X是素数吗？

对于X = 67的情况:

你怎么检查这个？

I divide it by 2... it has a remainder of 1 (this also tells us that 67 is an odd number)
I divide it by 3... it has a remainder of 1
I divide it by 4... it has a remainder of 3
I divide it by 5... it has a remainder of 2
I divide it by 6... it has a remainder of 1

事实上,如果数字不是素数,你只会得到0的余数.

你是否必须检查每个小于X的数字以确保它是素数？不.不再了,多亏了数学(!)

让我们看一个较小的数字,比如16.

16不是素数.

为什么？因为

2*8 = 16
4*4 = 16

因此,16可以均匀地除以1和它本身.(虽然"1"在技术上不是素数,但这是技术性的,我离题了)

所以我们将16除以1 ...当然这是有效的,这适用于每个数字

Divide 16 by 2... we get a remainder of 0  (8*2)
Divide 16 by 3... we get a remainder of 1  
Divide 16 by 4... we get a remainder of 0  (4*4)
Divide 16 by 5... we get a remainder of 1
Divide 16 by 6... we get a remainder of 4
Divide 16 by 7... we get a remainder of 2
Divide 16 by 8... we get a remainder of 0  (8*2)

我们实际上只需要一个0的余数来告诉我们它是复合的(与"素数"相反的是"复合").

检查16是否可被2整除与检查它是否可被8整除是一回事,因为2和8乘以得到16.

我们只需要检查一部分频谱(从2到X的平方根),因为我们可以乘的最大数是sqrt(X),否则我们使用较小的数来得到多余的答案.

17素数？

17 % 2 = 1
17 % 3 = 2
17 % 4 = 1 <--| approximately the square root of 17 [4.123...]
17 % 5 = 2 <--|
17 % 6 = 5
17 % 7 = 3

sqrt(X)之后的结果,类似17 % 7等等,是多余的,因为它们必须乘以小于sqrt(X)的东西才能得到X.

那是,

A*B = X.

如果A和B都大于sqrt(X)那么

A*B将产生一个大于X的数字.

因此,A或B中的一个必须小于sqrt(X),并且检查这两个值是多余的,因为您只需要知道其中一个是否均匀地划分X(偶数除法为您提供另一个值一个答案)

我希望有所帮助.

编辑:有更复杂的检查素数的方法,Java有一个内置的"这个数字可能是素数"或BigInteger类中的"这个数字肯定是复合的"方法,因为我最近通过另一个SO答案: