java - 改进计算素因子分解的算法

Question

我们正在进行以下编程练习:Primes in numbers .

任务是计算正数的质因数分解。

首先我们写了:

import java.util.*;
import java.math.*;

public class PrimeDecomp {
    public static String factors(int n) {
      System.out.println("\n\\n\n\n\n\n\n\n\nn: "+n);
      Map<Integer,Integer> map = new TreeMap<>();


      for(int i=1; n>1 && i<(n/2); i=1){
        System.out.println("out i: "+i);
        int prime = nextPrime(i);
        System.out.println("out prime: "+prime);
        while(n%prime!=0){
          i=prime;
          System.out.println("in i: "+i);
          prime = nextPrime(i);  
          System.out.println("in prime: "+prime);
        }
        n=n/prime;
        int count = map.containsKey(prime) ? map.get(prime) : 0;
        map.put(prime, count+1);
        System.out.println("map: "+map);
        System.out.println("\n\n\n\nnew n: "+n);
      }

      StringBuilder result = new StringBuilder();
      for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
        result.append(text);      
      }
      System.out.println("result: "+result);

      return result.toString();
    }

    public static int nextPrime(int n){
      BigInteger b = BigInteger.valueOf(n);
      return Integer.parseInt(b.nextProbablePrime().toString());
    }

}

当我们用 n = 35791357 测试前面的代码时，它耗尽了时间(执行时间超过 16000 毫秒)

我们决定使用另一种方法，不是每次迭代计算素数，而是一次计算所有素数，直到 n，如下所示:

import java.util.*;
import java.math.*;

public class PrimeDecomp {
    public static String factors(int n) {
      //System.out.println("\n\n\n\n\n\n\n\n\nn: "+n+"\n");
      Map<Integer,Integer> map = new TreeMap<>();
      List<Integer> primes = sieveOfEratosthenes(n);
      //System.out.println("primes: "+primes);

      for(int i=0; n>1 && i<(n/2); i=0){
        //System.out.println("out i: "+i);
        int prime = primes.get(i);
        //System.out.println("out prime: "+prime);
        while(n%prime!=0){
          prime = primes.get(++i);  
          //System.out.println("in i: "+i);
          //System.out.println("in prime: "+prime);
        }
        n=n/prime;
        int count = map.containsKey(prime) ? map.get(prime) : 0;
        map.put(prime, count+1);
        //System.out.println("map: "+map);
        //System.out.println("\n\n\n\nnew n: "+n);
      }

      StringBuilder result = new StringBuilder();
      for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
        result.append(text);      
      }
      System.out.println("result: "+result);

      return result.toString();
    }

    public static List<Integer> sieveOfEratosthenes(int n){
      boolean prime[] = new boolean[n+1];
      Arrays.fill(prime,true);
      for(int p=2; p*p<=n; p++){
        if(prime[p]){
          for(int i=p*2; i<=n; i+=p){
            prime[i]=false;
          }
        }
      }
      List<Integer> primeNumbers = new LinkedList<>();
      for(int i=2; i<=n; i++){
        if(prime[i]){
          primeNumbers.add(i);
        }
      }
      return primeNumbers;
    }

}

测试新代码后，我们观察到当 n = 933555431 时，执行超时。

我们考虑缓存上一次执行计算出的素数，这样算法就只需要计算上一次执行和新n之间的素数即可。

可以用伪代码解释为:

cachedPrimes = Create a static list to hold the calculated primes
primesCalculated = Create a static int to save until what n primes have been calculated

if primesCalculated < n
 cachedPrimes = Get the primes list from primesCalculated to n
 primesCalculated = n

我们开始起草代码如下:

import java.util.*;
import java.math.*;

public class PrimeDecomp {

    static List<Integer> cachedPrimes = new ArrayList<>();
    static int primesCalculated = 0;

    public static String factors(int n) {
      //System.out.println("\n\n\n\n\n\n\n\n\nn: "+n+"\n");
      Map<Integer,Integer> map = new TreeMap<>();
      List<Integer> primes = cachedPrimes;


      if(primesCalculated<n){
        if(primesCalculated==0){
          primes.addAll(sieveOfEratosthenes(2,n));
        }else{
          int diff = n - primesCalculated;
          primes.addAll(sieveOfEratosthenes(diff,n));
        }
        cachedPrimes = new ArrayList<Integer>(primes);
        primesCalculated = n;
      }

      //System.out.println("primes: "+primes);

      for(int i=0; i < primes.size() && n>1; i=0){
        //System.out.println("out i: "+i);
        int prime = primes.get(i);
        //System.out.println("out prime: "+prime);
        while(i < primes.size()-1 && n%prime!=0){
          prime = primes.get(++i);  
          //System.out.println("in i: "+i);
          //System.out.println("in prime: "+prime);
        }
        n=n/prime;
        int count = map.containsKey(prime) ? map.get(prime) : 0;
        map.put(prime, count+1);
        //System.out.println("map: "+map);
        //System.out.println("\n\n\n\nnew n: "+n);
      }

      StringBuilder result = new StringBuilder();
      for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
        result.append(text);      
      }
      //System.out.println("result: "+result);

      return result.toString();
    }

    public static List<Integer> sieveOfEratosthenes(int from, int to){
      boolean prime[] = new boolean[to+1];
      Arrays.fill(prime,true);
      for(int p=from; p*p<=to; p++){
        if(prime[p]){
          for(int i=p*2; i<=to; i+=p){
            prime[i]=false;
          }
        }
      }
      List<Integer> primeNumbers = new LinkedList<>();
      for(int i=from; i<=to; i++){
        if(prime[i]){
          primeNumbers.add(i);
        }
      }
      return primeNumbers;
    }

}

我们在尝试理解代码行为时遇到了困难。当我们执行练习的测试时，我们会看到:

“预期:61140377”，但实际是:933555431”

如果我们手动执行如下，n=61140377，它会通过:

import static org.junit.Assert.*;
import org.junit.*;

public class PrimeDecompTest { 
    @Test
    public void testPrimeDecompOne() {
        int lst = 7775460;        
        assertEquals(
            "(2**2)(3**3)(5)(7)(11**2)(17)",
            PrimeDecomp.factors(lst));

            lst = 61140377;        
        assertEquals(
            "(61140377)",
            PrimeDecomp.factors(lst));


    }

}

我们认为这是由于静态的cachedPrimes列表造成的。我们如何改进代码以缩短其执行时间并通过测试？

我们已阅读:

• https://www.baeldung.com/java-generate-prime-numbers
• https://www.geeksforgeeks.org/quick-ways-to-check-for-prime-and-find-next-prime-in-java/
• Java BigInteger prime numbers
• https://www.tutorialspoint.com/java/math/biginteger_probableprime.htm
• Converting from Integer, to BigInteger
• https://www.geeksforgeeks.org/biginteger-subtract-method-in-java-with-examples/
• Most efficient way to increment a Map value in Java
• Converting from Integer, to BigInteger
• How to sort Map values by key in Java?
• How do I efficiently iterate over each entry in a Java Map?
• Optimal way to find next prime number (Java)
• How do I join two lists in Java?
• https://www.geeksforgeeks.org/how-to-clone-a-list-in-java/

Answer 1

使用以下事实:

如果n不是质数，那么它有一个除数 d这样d*d <= n .

for (int divisor = 2; n > 1; ++divisor) {
    if (divisor * divisor >= n) {
        // n is prime, we have n**1 here
        break;
    }
    if (n % divisor == 0) {
        // divisor is a prime factor, divide n by it while we can
        int cnt = 0;
        while (n % divisor == 0) {
            n /= divisor;
            ++cnt;
        }
        // we have divisor**cnt here
    }
}

更新:该算法的复杂度为O(sqrt (n))