Улучшение алгоритма для вычисления разложения простых факторов

Question

Мы выполняем следующее упражнение по программированию: Простые числа в числах .

Задача состоит в том, чтобы вычислить декомпозицию простого множителя для положительного числа.

Сначала мы имеем записано:

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.

Это можно объяснить в псевдокоде. as:

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


    }

}

Мы думаем, что это связано со списком stati c 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 простые числа
• https://www.tutorialspoint.com/java/math/biginteger_probableprime.htm
• Преобразование из целого числа в BigInteger
• https://www.geeksforgeeks.org/biginteger-subtract-method-in-java-with-examples/
• Наиболее эффективный способ увеличения значения карты в Java
• Преобразование из целого числа в BigInteger
• Как отсортировать значения карты по ключу в Java?
• Как эффективно выполнить итерацию по каждой записи в Java Map?
• Оптимальный способ найти следующее простое число (Java)
• Как объединить два списка в 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))

Answer 2

Найдите в github.com / TilmanNeumann / java -мате-библиотеке более сложные алгоритмы целочисленной факторизации.