Java 中的质因数分解程序

Prime Factorization Program in Java

提问by kachilous

I am working on a prime factorization program implemented in Java. The goal is to find the largest prime factor of 600851475143 (Project Euler problem 3). I think I have most of it done, but I am getting a few errors. Also my logic seems to be off, in particular the method that I have set up for checking to see if a number is prime.

我正在研究用 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;
    }
}

Edit

编辑

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;
    }
}

采纳答案by Stephen C

Why make it so complicated? You don't needdo anything like isPrime(). Divide it's least divisor(prime) and do the loop from this prime. Here is my simple code :

为什么要弄得这么复杂？你不需要做任何像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));
    }
}

回答by shoebox639

You want to iterate from 2 -> n-1 and make sure that n % i != 0. That's the most naive way to check for primality. As explained above, this is very very slow if the number is large.

您想从 2 -> n-1 迭代并确保 n % i != 0。这是检查素性的最幼稚的方法。如上所述，如果数量很大，这将非常非常慢。

回答by amer

I think you're confused because there is no iff [if-and-only-if] operator.

我认为您很困惑，因为没有 iff [if-and-only-if] 运算符。

Going to the square root of the integer in question is a good shortcut. All that remains is checking if the number within that loop divides evenly. That's simply [big number] % i == 0. There is no reason for your Prime function.

求有问题的整数的平方根是一个很好的捷径。剩下的就是检查该循环中的数字是否被平均分割。这只是 [big number] % i == 0。没有理由使用您的 Prime 函数。

Since you are looking for the largest divisor, another trick would be to start from the highest integer less than the square root and go i--.

由于您正在寻找最大的除数，另一个技巧是从小于平方根的最高整数开始并转到 i--。

Like others have said, ultimately, this is brutally slow.

就像其他人所说的那样，最终，这是非常缓慢的。

回答by Jerry Coffin

To find factors, you want something like:

要查找因素，您需要以下内容：

long limit = sqrt(number);
for (long i=3; i<limit; i+=2)
    if (number % i == 0)
        print "factor = " , i;

In this case, the factors are all small enough (<7000) that finding them should take well under a second, even with naive code like this. Also note that this particular number has other, smaller, prime factors. For a brute force search like this, you can save a little work by dividing out the smaller factors as you find them, and then do a prime factorization of the smaller number that results. This has the advantage of only giving prime factors. Otherwise, you'll also get composite factors (e.g., this number has four prime factors, so the first method will print out not only the prime factors, but the products of various combinations of those prime factors).

在这种情况下，这些因素都足够小（<7000），即使使用像这样的简单代码，也应该在一秒钟内找到它们。另请注意，此特定数字还有其他较小的质因数。对于像这样的蛮力搜索，您可以通过在找到较小的因子时将它们分开，然后对结果的较小数进行质因数分解来节省一些工作。这具有仅给出素因数的优点。否则，您还会得到复合因数（例如，这个数有四个质因数，所以第一种方法不仅会打印出质因数，还会打印出这些质因数的各种组合的乘积）。

If you want to optimize that a bit, you can use the sieve of Eratosthenes to find the prime numbers up to the square root, and then only attempt division by primes. In this case, the square root is ~775'000, and you only need one bit per number to signify whether it's prime. You also (normally) only want to store odd numbers (since you know immediately that all even numbers but two are composite), so you need ~775'000/2 bits = ~47 Kilobytes.

如果你想稍微优化一下，你可以使用 Eratosthenes 的筛子来找到直到平方根的素数，然后只尝试除以素数。在这种情况下，平方根是 ~775'000，每个数字只需要一位来表示它是否是素数。您还（通常）只想存储奇数（因为您立即知道除两个之外的所有偶数都是复合数），因此您需要 ~775'000/2 位 = ~47 KB。

In this case, that has little real payoff though -- even a completely naive algorithm will appear to produce results instantly.

在这种情况下，这几乎没有真正的回报——即使是一个完全幼稚的算法也会立即产生结果。

回答by sova

edit: I hope this doesn't sound incredibly condescending as an answer. I just really wanted to illustrate that from the computer's point of view, you have to check all possible numbers that could be factors of X to make sure it's prime. Computers don't knowthat it's composite just by looking at it, so you have to iterate

编辑：我希望这听起来不是令人难以置信的居高临下的回答。我只是想从计算机的角度说明这一点，您必须检查所有可能是 X 因数的数字，以确保它是质数。计算机不知道它是复合的，只是看它，所以你必须迭代

Example: Is X a prime number?

例子：X 是质数吗？

For the case where X = 67:

对于 X = 67 的情况：

How do you check this?

你如何检查这个？

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

In fact, you will only get a remainder of 0 if the number is not prime.

事实上，如果数字不是质数，你只会得到 0 的余数。

Do you have to check every single number less than X to make sure it's prime? Nope. Not anymore, thanks to math (!)

您是否必须检查每个小于 X 的数字以确保它是质数？不。不再，感谢数学（！）

Let's look at a smaller number, like 16.

让我们看一个更小的数字，比如 16。

16 is not prime.

16 不是素数。

why? because

为什么？因为

2*8 = 16
4*4 = 16

So 16 is divisible evenly by more than just 1 and itself. (Although "1" is technically not a prime number, but that's technicalities, and I digress)

所以 16 不仅可以被 1 和它本身整除。（虽然“1”在技术上不是质数，但这是技术性的，我离题了）

So we divide 16 by 1... of course this works, this works for every number

所以我们将 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)

We really only need one remainder of 0 to tell us it's composite (the opposite of "prime" is "composite").

我们真的只需要 0 的一个余数来告诉我们它是复合的（“素数”的反义词是“复合”）。

Checking if 16 is divisible by 2 is the same thing as checking if it's divisible by 8, because 2 and 8 multiply to give you 16.

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

We only need to check a portion of the spectrum (from 2 up to the square-root of X) because the largest number that we can multiply is sqrt(X), otherwise we are using the smaller numbers to get redundant answers.

我们只需要检查一部分频谱（从 2 到 X 的平方根），因为我们可以相乘的最大数是 sqrt(X)，否则我们将使用较小的数来获得冗余答案。

Is 17 prime?

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

The results after sqrt(X), like 17 % 7and so on, are redundant because they must necessarily multiply with something smaller than the sqrt(X) to yield X.

sqrt(X) 之后的结果17 % 7是多余的，因为它们必须乘以小于 sqrt(X) 的值才能产生 X。

That is,

那是，

A * B = X

A * B = X

if A and B are both greater than sqrt(X) then

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

A*B will yield a number that is greater than X.

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

Thus, one of either A or B must be smaller than sqrt(X), and it is redundant to check both of these values since you only need to know if one of them divides X evenly (the even division gives you the other value as an answer)

因此，A 或 B 中的一个必须小于 sqrt(X)，检查这两个值是多余的，因为您只需要知道它们中的一个是否将 X 平均除（偶数除法为您提供另一个值作为一个答案）

I hope that helps.

我希望这有帮助。

edit: There are more sophisticated methods of checking primality and Java has a built-in "this number is probably prime" or "this number is definitely composite" method in the BigInteger classas I recently learned via another SO answer :]

编辑：有更复杂的检查素数的方法，Java 在BigInteger 类中有一个内置的“这个数字可能是素数”或“这个数字肯定是复合的”方法，因为我最近通过另一个 SO 答案了解到：]

回答by Stephen C

You need to do some research on algorithms for factorizing largenumbers; this wikipedia pagelooks like a good place to start. In the first paragraph, it states:

您需要对分解大数的算法进行一些研究；这个维基百科页面看起来是个不错的起点。在第一段中，它指出：

When the numbers are very large, no efficient integer factorization algorithm is publicly known ...

当数字非常大时，没有公知的有效整数分解算法......

but it does list a number of special and general purpose algorithms. You need to pick one that will work well enough to deal with 12 decimal digit numbers. These numbers are too large for the most naive approach to work, but small enough that (for example) an approach based on enumerating the prime numbers starting from 2 would work. (Hint - start with the Sieve of Erasthones)

但它确实列出了许多特殊和通用的算法。您需要选择一个可以很好地处理 12 位十进制数字的方法。这些数字对于最简单的方法来说太大了，但足够小以至于（例如）基于枚举从 2 开始的素数的方法可以工作。（提示 - 从 Erasthones 筛开始）

回答by Stijak

Here is very elegant answer - which uses brute force (not some fancy algorithm) but in a smart way - by lowering the limit as we find primes and devide composite by those primes...

这是一个非常优雅的答案 - 它使用蛮力（不是一些花哨的算法），而是以一种聪明的方式 - 通过在我们找到素数并通过这些素数除以复合物时降低限制......

It also prints only the primes - and just the primes, and if one prime is more then once in the product - it will print it as many times as that prime is in the product.

它也只打印素数 - 并且只打印素数，如果一个素数在乘积中超过一次 - 它会打印与乘积中那个素数一样多的次数。

    public class Factorization {
    public static void main(String[] args) {
    long composite = 600851475143L;
    int limit = (int)Math.sqrt(composite)+1;
    for (int i=3; i<limit; i+=2)
    {
        if (composite%i==0)
        {
            System.out.println(i);
            composite = composite/i;
            limit = (int)Math.sqrt(composite)+1;
            i-=2;   //this is so it could check same prime again
        }
    }
    System.out.println(composite);
    }
}

回答by user2069283

    private static boolean isPrime(int k) throws IllegalArgumentException
     {
        int j;

        if (k < 2) throw new IllegalArgumentException("All prime numbers are greater than 1.");
        else {
            for (j = 2; j < k; j++) {
                if (k % j == 0) return false;
            }
        }

        return true;
    }

    public static void primeFactorsOf(int n) {
        boolean found = false;

        if (isPrime(n) == true) System.out.print(n + " ");
        else {
            int i = 2;
            while (found == false) {
                if ((n % i == 0) && (isPrime(i))) {
                    System.out.print(i + ", ");
                    found = true;
                } else i++;
            }
            primeFactorsOf(n / i);
        }
    }

回答by Ben Colson

For those answers which use a method isPrime(int) : boolean, there is a faster algorithm than the one previously implemented (which is something like)

对于那些使用方法的答案isPrime(int) : boolean，有比以前实现的算法更快的算法（类似于）

private static boolean isPrime(long n) { //when n >= 2
    for (int k = 2; k < n; k++)
        if (n % k == 0) return false;

    return true;
}

and it is this:

这是这样的：

private static boolean isPrime(long n) { //when n >= 2
    if (n == 2 || n == 3) return true;

    if (n % 2  == 0 || n % 3 == 0) return false;

    for (int k = 1; k <= (Math.floor(Math.sqrt(n)) + 1) / 6; k++)
        if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0) return false;

    return true;
}

I made this algorithm using two facts:

我使用两个事实制作了这个算法：

1. We only need to check for n % k == 0up to k <= Math.sqrt(n). This is true because for anything higher, factors merely "flip" ex. consider the case n = 15, where 3 * 5= 5 * 3, and 5> Math.sqrt(15). There is no need for this overlap of checking both 15 % 3 == 0and 15 % 5 == 0, when we could just check one of these expressions.
2. All primes (excluding 2and 3) can be expressed in the form (6 * k) + 1or (6 * k) - 1, because any positive integer can be expressed in the form (6 * k) + n, where n = -1, 0, 1, 2, 3, or 4and kis an integer <= 0, and the cases where n = 0, 2, 3, and 4are all reducible.

1. 我们只需要检查n % k == 0最多k <= Math.sqrt(n). 这是真的，因为对于任何更高的东西，因素只是“翻转”例如。考虑这种情况n = 15，其中3 * 5=5 * 3和5> Math.sqrt(15)。当我们可以只检查这些表达式中的一个时，不需要检查15 % 3 == 0和的这种重叠15 % 5 == 0。
2. 所有素数（不包括2和3）都可以用(6 * k) + 1or的形式表示(6 * k) - 1，因为任何正整数都可以用 的形式表示(6 * k) + n，其中n = -1, 0, 1, 2, 3, or 4和k是整数<= 0，并且 where 的情况n = 0, 2, 3, and 4都是可约的。

Therefore, nis prime if it is not divisible by 2, 3, or some integer of the form 6k ± 1 <= Math.sqrt(n). Hence the above algorithm.

因此，n是素数，如果它不能被整除2，3或某种形式的整数6k ± 1 <= Math.sqrt(n)。因此上面的算法。

--

——

Wikipedia article on testing for primality

维基百科关于素数测试的文章

--

——

Edit: Thought I might as well post my full solution (*I did not use isPrime(), and my solution is nearly identical to the top answer, but I thought I should answer the actual question):

编辑：我想我不妨发布我的完整解决方案（*我没有使用isPrime()，我的解决方案几乎与最佳答案相同，但我认为我应该回答实际问题）：

public class Euler3 {

    public static void main(String[] args) {
        long[] nums = {13195, 600851475143L};

        for (num : nums)
            System.out.println("Largest prime factor of " + num + ": " + lpf(num));

    }

    private static lpf(long n) {
        long largestPrimeFactor = 1;
        long maxPossibleFactor = n / 2;

        for (long i = 2; i <= maxPossibleFactor; i++)
            if (n % i == 0) {
                n /= i;
                largestPrimeFactor = i;

                i--;
            }

            return largestPrimeFactor;

    }

}

回答by OSezer

To find all prime factorization

找到所有的质因数分解

import java.math.BigInteger;
import java.util.Scanner;


public class BigIntegerTest {


     public static void main(String[] args) {


            BigInteger myBigInteger = new BigInteger("65328734260653234260");//653234254
            BigInteger originalBigInteger;
            BigInteger oneAddedOriginalBigInteger;
            originalBigInteger=myBigInteger;
            oneAddedOriginalBigInteger=originalBigInteger.add(BigInteger.ONE);
            BigInteger index;
            BigInteger countBig;


            for (index=new BigInteger("2");  index.compareTo(myBigInteger.add(BigInteger.ONE)) <0; index = index.add(BigInteger.ONE)){

                countBig=BigInteger.ZERO;
                while(myBigInteger.remainder(index) == BigInteger.ZERO ){
                    myBigInteger=myBigInteger.divide(index);
                    countBig=countBig.add(BigInteger.ONE);
                }

                if(countBig.equals(BigInteger.ZERO)) continue;
                System.out.println(index+ "**" + countBig);

            }
            System.out.println("Program is ended!");
     }
}