Java中的质因数分解程序

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

- kachilous

---

你遇到了哪些错误？在哪些行出现了错误？ - Eternal Noob

您的Prime方法总是返回true，因为所有数字都可以被它们自己和1整除，即n%n == 0 && n%1 == 0。但是您缺少定义中的“仅”这个词。 - Aaron Novstrup

@Adam，我想你的意思是“可被它们自己和_1_整除”。 - paxdiablo

哎呀，是的。没有足够的注意力。Krysten：这里不适用平方根。如果600851475143是一个质数的三倍，你需要检查它的1/3。此外，在isPrime循环中，你从哪里得到这个700K？你需要迭代到数字，而不是7K，这样你的函数才会对除2以外的所有值返回false。那是平方根，但它在那里没有任何作用。 - Adam Norberg

@Adam，所以我改变了isPrime方法，让它循环到number，但现在对于我的main方法中的循环，我需要迭代到600851475143，是吗？@Jesper，是的。 - kachilous

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

- user467871

---

小提示：如果要处理大于2147483647（Integer.MAX_VALUE）的大质数，也许你应该将变量“i”的类型设置为long。 - kisp

@kisp 为什么我们要执行 i--？ - user6857832

你在考验我吗？;) 这个循环按顺序从最小的因子开始。一个数字可以被同样的数除多次，比如2 * 2 * 2 * 2。 - kisp

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

对于像 17 % 7 这样的sqrt(X)后的结果是多余的，因为它们必须与小于sqrt(X)的某个数相乘才能得到X。

也就是说，如果A和B都大于sqrt(X)，则A * B将产生一个大于X的数。

因此，要么A要么B必须小于sqrt(X)，检查这些值中的任意一个是否可以整除X就足够了（如果可以，另一个值将成为答案）。

希望这有所帮助。

编辑：还有更复杂的检查素数方法，Java在 BigInteger 类中内置了“该数字可能是素数”或“该数字明确是合数”的方法，我最近通过 SO 上的另一个答案学到了这一点 :]

- sova

Answer 3

你需要研究一些用于分解大数的算法；这个维基百科页面看起来是一个不错的开始。在第一段中，它指出：

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

但它列出了许多特殊和通用算法。你需要选择一个足够好的算法来处理12位十进制数字。这些数字对于最简单的方法来说太大了，但对于例如基于从2开始枚举素数的方法来说则太小了（提示-从埃拉托斯特尼筛选法开始）。

- Stephen C

---

实际上，对于这么大的数，最朴素的方法仍然可以运行良好。我使用了600852871609进行了快速更改，它等于775147的平方，并且进行了一个朴素测试（虽然是用C++而不是Java），仍然得到了看起来是瞬间的结果（计时显示小于0.1秒）。 - Jerry Coffin

@Jerry - 这取决于你测试每个数字是否为质数的方式有多么天真。我在这里尽量含糊其辞，以鼓励原帖作者自己解决问题。 - Stephen C

Answer 4

这里有一个非常优雅的答案——它使用了暴力方法（而不是一些花哨的算法），但是以聪明的方式——通过在找到质数并将合成数除以这些质数时降低限制...... 它还只打印质数 - 只打印质数，如果一个质数在乘积中出现多次 - 它将打印与该质数相同数量的次数。

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

- Stijak

---

我刚刚注意到它会完全忽略二的倍数（尽管在输入数字时很容易看出该数字是否为偶数）- 在此循环之前可能还有另一个while(composite%2==0)来检查它自身有多少个二因子... - Stijak

Answer 5

您希望从2 -> n-1进行迭代，并确保n % i != 0。这是检查素数的最朴素方法。如上所述，如果数字很大，这种方法非常非常慢。

- shoebox639

Answer 6

要寻找因子，您需要像这样的内容：

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

在这种情况下，因数都足够小（＜7000），即使使用像这样的朴素代码，找到它们也应该不到一秒钟。还要注意，这个特定的数字有其他更小的质因数。对于像这样的暴力搜索，您可以在找到它们时除掉较小的因子，然后对结果进行质因数分解。这样做的好处是仅提供质因数。否则，您还将获得组合因子（例如，此数字有四个质因数，因此第一种方法将打印出各种组合的质因数乘积）。

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

在这种情况下，这几乎没有实际回报-即使完全朴素的算法似乎也会立即产生结果。

- Jerry Coffin

---

如果你只是检查i是否可以被整除，那么怎么知道i是质数呢？ - kachilous

@Krysten：你不会这样做的。正如我所说，这个程序可以找到因子，而不仅仅是质因数。但是我已经编辑了答案，添加了一种只显示质因数的方法。 - Jerry Coffin

@Krysten：29是一个质数，因为没有比29小的数可以整除它。2到28之间的任何数都不能被29整除而不产生余数或分数部分。因此，您可以通过将一个数字除以它以下的每个整数来确定它是否为质数。您还可以注意到，您只需要将其除以要检查的数字的平方根之前的每个数字即可，这是因为... [我会在答案中详细说明以获得更多空间/格式] - sova

Answer 7

我认为你感到困惑是因为没有iff [if-and-only-if]运算符。

对问题中的整数进行平方根是一个好的快捷方式。剩下的就是检查循环内的数字是否可以被整除。这很简单，即[大数字] % i == 0。没有必要使用Prime函数。

由于您正在寻找最大的除数，另一个技巧是从小于平方根的最高整数开始，然后递减i。

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

- amer

---

你可以始终检查2，从3开始，并在每一步增加i 2个单位，以将时间减半。这是提高确定素数方法的简单方式。 - AndyPerfect

Answer 8

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

- user2069283

---

无法处理 600851475149。 - Will Ness

Answer 9

public class Prime
{
 int i;   

 public Prime( )
 {
    i = 2;
 }

 public boolean isPrime( int test ) 
 {
    int k;

    if( test < 2 )
        return false;
    else if( test == 2 )  
        return true;
    else if( ( test > 2 ) && ( test % 2 == 0 ) )
        return false;
    else
    {
        for( k = 3; k < ( test/2 ); k += 2 )
        {
            if( test % k == 0 ) 
                return false;
        }

    }

    return true;

 }

 public void primeFactors( int factorize )
 {
    if( isPrime( factorize ) )
    {
        System.out.println( factorize );
        i = 2;
    }
    else
    {
        if( isPrime( i ) && ( factorize % i == 0 ) )
        {
            System.out.print( i+", " );
            primeFactors( factorize / i );
        }
        else
        {
            i++;
            primeFactors( factorize );
        }
   }

   public static void main( String[ ] args )
   {
       Prime p = new Prime( );

       p.primeFactors( 649 );
       p.primeFactors( 144 );
       p.primeFactors( 1001 );
   }
}

- user2710322

Answer 10

我在编程课上遇到了一个非常类似的问题。在我的课堂上，需要计算输入的数字。我使用了和Stijak非常相似的解决方案。我编辑了我的代码，以解决这个问题而不使用输入。

与Stijak的代码有一些不同之处:

我在我的代码中考虑了偶数。

我的代码只打印最大的质因数，而不是所有的因数。

直到我将当前因子的所有实例除尽之前，我不会重新计算factorLimit。

我将所有变量声明为长整型，因为我希望能够处理非常大的数字。我发现最坏的情况是像9223372036854775783这样的非常大的素数，或者像9223371994482243049这样的具有素数平方根的非常大的数字。数字拥有的因子越多，算法运行得越快。因此，最理想的情况是像4611686018427387904（2^62）或6917529027641081856（3*2^61）这样的数字，因为它们都有62个因子。

public class LargestPrimeFactor
{
    public static void main (String[] args){
        long number=600851475143L, factoredNumber=number, factor, factorLimit, maxPrimeFactor;
        while(factoredNumber%2==0)
            factoredNumber/=2;
        factorLimit=(long)Math.sqrt(factoredNumber);
        for(factor=3;factor<=factorLimit;factor+=2){
            if(factoredNumber%factor==0){
                do  factoredNumber/=factor;
                while(factoredNumber%factor==0);
                factorLimit=(long)Math.sqrt(factoredNumber);
            }
        }
        if(factoredNumber==1)
            if(factor==3)
                maxPrimeFactor=2;
            else
                maxPrimeFactor=factor-2;
        else
            maxPrimeFactor=factoredNumber;
        if(maxPrimeFactor==number)
            System.out.println("Number is prime.");
        else
            System.out.println("The largest prime factor is "+maxPrimeFactor);
    }
}

- Steven Smith