Courses/CS 460/Fall 2006/Prime Factorization

From CSWiki

[edit] Problem

Factor a number (given in main()) and return a list of prime factors.

Strategy: Construct an array IntDomainVar[] primes.

// There can't be more than log2(numberToFactor) primes
int maxPrimeCount = (int) (Math.log10(numberToFactor)/Math.log10(2));  
IntDomainVar[] primes = IntDomainVar[maxPrimeCount];

Require the product of the primes be the number to factor. Minimize the sum of the primes. Since A * B > A + B if A >= 2 and B >= 2 and either A > 2 or B > 2, minimizing the sum of the factors will ensure that the factors are prime. (If a factor could be factored, the sum of its factors would be smaller than itself. This is not true 4, but since unused positions in the primes array contribute a 1 to the sum, factoring 4 into 2*2 reduces the contribution of sum([4, 1]) = 5 to sum([2, 2]) = 4.

[edit] Code

package examples;

import java.util.ArrayList;

import choco.Problem;
import choco.integer.IntDomainVar;

public class PrimeFactorization {

  public static Problem problem;

  public static void main(String[] args) {
    int numberToFactor = 210;
    ArrayList<IntDomainVar> primes = findPrimeFactors(numberToFactor);
    System.out.print(numberToFactor);
    if (!problem.isFeasible()) {
      System.out.println(" is prime.");
      return;
    }
    System.out.print(" = ");
    boolean needTimesSign = false;
      for (IntDomainVar prime: primes) {
      System.out.print((needTimesSign ? " * " : "") + prime.getVal());
      needTimesSign = true;
    }
    System.out.println();
  }

  private static ArrayList<IntDomainVar> findPrimeFactors(int numberToFactor) {
    problem = new Problem();
    // There can't be more than log2(numberToFactor) primes
    int maxPrimeCount = (int) (Math.log10(numberToFactor)/Math.log10(2));  
    IntDomainVar[] primes = new IntDomainVar[maxPrimeCount];   
    for (int i = 0; i < maxPrimeCount; i++) {
      // Allow unused primes to be 1. There may be fewer than maxPrimeCount primes.
      primes[i] = problem.makeEnumIntVar("prime[" + i + "]", 1, numberToFactor/2);
      if (i > 0) problem.post(problem.geq(primes[i-1], primes[i]));
    }

    imposeProduct(primes, numberToFactor);
    IntDomainVar primeSum = problem.makeBoundIntVar("primeSum", 2, numberToFactor);
    problem.post(problem.eq(primeSum, problem.sum(primes)));
    problem.minimize(primeSum, false); 
    
    ArrayList<IntDomainVar> primeFactors = new ArrayList<IntDomainVar>();
    for (IntDomainVar prime: primes) {
      if (!prime.isInstantiated() || prime.getVal() == 1) continue;
      primeFactors.add(prime);
    }
    return primeFactors;
  }

  private static void imposeProduct(IntDomainVar[] terms, int product) {
    IntDomainVar oldProd = terms[0];
    for (int i = 1; i < terms.length; i++) {
      IntDomainVar newProd = problem.makeEnumIntVar("prod("+i + ")", 
                                                    i < terms.length - 1 ? 0 : product, 
                                                    product);
      problem.post(problem.times(oldProd, terms[i], newProd));
      oldProd = newProd;
    }
  }
  
}

[edit] Output

The number to factor was given as 210.

210 = 7 * 5 * 3 * 2

However, if the order of the factors is required to be reversed, i.e., the line in findPrimeFactors(int numberToFactor)

if (i > 0) problem.post(problem.geq(primes[i-1], primes[i]));

is changed to

if (i > 0) problem.post(problem.leq(primes[i-1], primes[i]));

the output is

210 = 2 * 105

I don't understand why this happens.