1:  package de.luschny.math.factorial;
   2:   
   3:  import de.luschny.math.Xmath;
   4:  import de.luschny.math.arithmetic.Xint;
   5:  import de.luschny.math.primes.IPrimeIteration;
   6:  import de.luschny.math.primes.PrimeSieve;
   7:   
   8:  public class FactorialPrimeSwing implements IFactorialFunction
   9:  {
  10:   
  11:      private PrimeSieve sieve;
  12:      private int[] primeList;
  13:   
  14:      public FactorialPrimeSwing()
  15:      {
  16:      }
  17:   
  18:      public String getName()
  19:      {
  20:          return "PrimeSwing        ";
  21:      }
  22:   
  23:      public Xint factorial(int n)
  24:      {
  25:          // For very small n the 'NaiveFactorial' is OK.
  26:          if (n < 20)    { return Xmath.Factorial(n); }
  27:   
  28:          sieve = new PrimeSieve(n);
  29:          int pLen = (int)sieve.getIteration().getNumberOfPrimes();
  30:          primeList = new int[pLen];
  31:   
  32:          return recFactorial(n).shiftLeft(n - Integer.bitCount(n));
  33:      }
  34:   
  35:      private Xint recFactorial(int n)
  36:      {
  37:          if (n < 2)
  38:          {
  39:              return Xint.ONE;
  40:          }
  41:          return recFactorial(n / 2).square().multiply(swing(n));
  42:      }
  43:   
  44:      private Xint swing(int n)
  45:      {
  46:          if (n < 33)
  47:          {
  48:              return Xint.valueOf(smallOddSwing[n]);
  49:          }
  50:   
  51:          int sqrtN = (int) Math.floor(Math.sqrt(n));
  52:          IPrimeIteration pIter0 = sieve.getIteration(3, sqrtN);
  53:          IPrimeIteration pIter1 = sieve.getIteration(sqrtN + 1, n / 3);
  54:   
  55:          int count = 0;
  56:   
  57:          for (int prime : pIter0)
  58:          {
  59:              int q = n, p = 1;
  60:   
  61:              while ((q /= prime) > 0)
  62:              {
  63:                  if ((q & 1) == 1)
  64:                  {
  65:                      p *= prime;
  66:                  }
  67:              }
  68:   
  69:              if (p > 1)
  70:              {
  71:                  primeList[count++] = p;
  72:              }
  73:          }
  74:   
  75:          for (int prime : pIter1)
  76:          {
  77:              if (((n / prime) & 1) == 1)
  78:              {
  79:                  primeList[count++] = prime;
  80:              }
  81:          }
  82:   
  83:          Xint prod = sieve.getPrimorial(n / 2 + 1, n);
  84:          return prod.multiply(primeList, count);
  85:      }
  86:   
  87:      private static int[] smallOddSwing =
  88:          { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 
  89:            6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 
  90:            2028117, 676039, 16900975, 1300075, 35102025, 5014575,
  91:            145422675, 9694845, 300540195, 300540195 };
  92:      
  93:  } // endOfFactorialPrimeSwingLuschny