Integer factorization

Computes an integer factorization of $n using
trial division and a cached sieve of computed primes

@param type var Description
338094
public static function ifactor($n)
    {

        // max_n = 2^31-1 = 2147483647
        $d = 2;
        $factors = [];
        $dmax = floor(sqrt($n));

        self::$sieve = array_pad(self::$sieve, $dmax, 1);

        do {
            $r = false;
            while ($n % $d == 0) {
                if (array_key_exists($d, $factors)) {
                    $factors[$d]++;
                } else {
                    $factors[$d] = 1;
                }

                $n /= $d;
                $r = true;
            }
            if ($r) {
                $dmax = floor(sqrt($n));
            }
            if ($n > 1) {
                for ($i = $d; $i <= $dmax; $i += $d) {
                    self::$sieve[$i] = 0;
                }
                do {
                    $d++;
                } while ($d < $dmax && self::$sieve[$d] != 1);

                if ($d > $dmax) {
                    if (array_key_exists($n, $factors)) {
                        $factors[$n]++;
                    } else {
                        $factors[$n] = 1;
                    }
                }
            }
        } while ($n > 1 && $d <= $dmax);

        return $factors;
    }
154426
protected int pushTypeVariables () {
		GenericType[] genericTypes = kryo.getGenerics().nextGenericTypes();
		if (genericTypes == null) return 0;

		int pop = kryo.getGenerics().pushTypeVariables(genericsHierarchy, genericTypes);
		if (TRACE && pop > 0) trace("kryo", "Generics: " + kryo.getGenerics());
		return pop;
	}
341879
void addVar(TypeVar t) {
        this.undetvars = this.undetvars.prepend(infer.fromTypeVarFun.apply(t));
        this.inferencevars = this.inferencevars.prepend(t);
    }
331362
function BigInteger(a, b) {
    if (a != null) {
        if ("number" == typeof a) {
            this.fromNumber(a, b);
        } else if (Buffer.isBuffer(a)) {
            this.fromBuffer(a);
        } else if (b == null && "string" != typeof a) {
            this.fromByteArray(a);
        } else {
            this.fromString(a, b);
        }
    }
}
675278
private int getIndex(TypeVariable<?> variable) {

        Class<?> rawType = resolveClass(owningType);
        TypeVariable<?>[] typeParameters = rawType.getTypeParameters();

        for (int i = 0; i < typeParameters.length; i++) {
            if (variable.equals(typeParameters[i])) {
                return i;
            }
        }

        return -1;
    }
508865
function inferrableVariableVisitor(node) {
            if (!node.id) {
                return;
            }
            reportInferrableType(node, node.id.typeAnnotation, node.init);
        }
847049
function factorizeHash(n) {
    let factors = {};
    factorize(n, factor => {
        if (factors[factor]) {
            factors[factor] += 1;
        } else {
            factors[factor] = 1;
        }
    });
    return factors;
}
158878
function randProbPrimeRounds(k,n) {
    var ans, i, divisible, B; 
    B=30000;  //B is largest prime to use in trial division
    ans=int2bigInt(0,k,0);
    
    //optimization: try larger and smaller B to find the best limit.
    
    if (primes.length==0)
      primes=findPrimes(30000);  //check for divisibility by primes <=30000

    if (rpprb.length!=ans.length)
      rpprb=dup(ans);

    for (;;) { //keep trying random values for ans until one appears to be prime
      //optimization: pick a random number times L=2*3*5*...*p, plus a 
      //   random element of the list of all numbers in [0,L) not divisible by any prime up to p.
      //   This can reduce the amount of random number generation.
      
      randBigInt_(ans,k,0); //ans = a random odd number to check
      ans[0] |= 1; 
      divisible=0;
    
      //check ans for divisibility by small primes up to B
      for (i=0; (i<primes.length) && (primes[i]<=B); i++)
        if (modInt(ans,primes[i])==0 && !equalsInt(ans,primes[i])) {
          divisible=1;
          break;
        }      
      
      //optimization: change millerRabin so the base can be bigger than the number being checked, then eliminate the while here.
      
      //do n rounds of Miller Rabin, with random bases less than ans
      for (i=0; i<n && !divisible; i++) {
        randBigInt_(rpprb,k,0);
        while(!greater(ans,rpprb)) //pick a random rpprb that's < ans
          randBigInt_(rpprb,k,0);
        if (!millerRabin(ans,rpprb))
          divisible=1;
      }
      
      if(!divisible)
        return ans;
    }  
  }
892737
private static boolean hasTypeVariables(final Type type) {
        if (type instanceof TypeVariable<?> || type instanceof GenericArrayType) {
            return true;
        } else if (type instanceof ParameterizedType) {
            for (final Type arg : ((ParameterizedType) type).getActualTypeArguments()) {
                if (hasTypeVariables(arg)) {
                    return true;
                }
            }
        }
        return false;
    }
386777
private static Iterator<int[]> initializeValueIterator(VariableNumMap vars) {
		int[] dimensionSizes = new int[vars.size()];
		
		List<DiscreteVariable> discreteVars = vars.getDiscreteVariables();
		for (int i = 0; i < discreteVars.size(); i++) {
		  dimensionSizes[i] = discreteVars.get(i).numValues();
		}
		return new IntegerArrayIterator(dimensionSizes, new int[0]);
	}
1106783
@SuppressWarnings( "unchecked" )
    private FieldMetadata processVariableDeclaration( SingleVariableDeclaration singleVariableDeclaration,
                                                      Type type ) {

        Variable variable;
        if (type.isPrimitiveType()) {
            FieldMetadata primitiveFieldMetadata = FieldMetadata.primitiveType(((PrimitiveType)type).getPrimitiveTypeCode().toString());
            variable = new Variable();
            variable.setName(JavaMetadataUtil.getName(singleVariableDeclaration.getName()));
            primitiveFieldMetadata.setName(variable.getName());

            primitiveFieldMetadata.getVariables().add(variable);
            for (IExtendedModifier extendedModifier : (List<IExtendedModifier>)singleVariableDeclaration.modifiers()) {
                if (extendedModifier.isAnnotation()) {
                    primitiveFieldMetadata.getAnnotations().add(createAnnotationMetadataFor((Annotation)extendedModifier));
                } else {
                    Modifier modifier = (Modifier)extendedModifier;
                    primitiveFieldMetadata.getModifiers().add(new ModifierMetadata(modifier.getKeyword().toString()));
                }
            }
            return primitiveFieldMetadata;
        }
        if (type.isSimpleType()) {
            SimpleType simpleType = (SimpleType)type;
            FieldMetadata simpleTypeFieldMetadata = FieldMetadata.simpleType(JavaMetadataUtil.getName(simpleType.getName()));
            variable = new Variable();
            variable.setName(JavaMetadataUtil.getName(singleVariableDeclaration.getName()));
            simpleTypeFieldMetadata.setName(variable.getName());
            simpleTypeFieldMetadata.getVariables().add(variable);
            for (IExtendedModifier simpleTypeExtendedModifier : (List<IExtendedModifier>)singleVariableDeclaration.modifiers()) {
                if (simpleTypeExtendedModifier.isAnnotation()) {
                    simpleTypeFieldMetadata.getAnnotations().add(createAnnotationMetadataFor((Annotation)simpleTypeExtendedModifier));
                } else {
                    Modifier modifier = (Modifier)simpleTypeExtendedModifier;
                    simpleTypeFieldMetadata.getModifiers().add(new ModifierMetadata(modifier.getKeyword().toString()));
                }
            }
            return simpleTypeFieldMetadata;
        }
        if (type.isParameterizedType()) {
            ParameterizedType parameterizedType = (ParameterizedType)type;
            FieldMetadata parameterizedTypeFieldMetadata = FieldMetadata.parametrizedType(getTypeName(parameterizedType));

            variable = new Variable();
            variable.setName(JavaMetadataUtil.getName(singleVariableDeclaration.getName()));
            parameterizedTypeFieldMetadata.setName(variable.getName());
            parameterizedTypeFieldMetadata.getVariables().add(variable);
            for (IExtendedModifier parameterizedExtendedModifier : (List<IExtendedModifier>)singleVariableDeclaration.modifiers()) {
                if (parameterizedExtendedModifier.isAnnotation()) {
                    parameterizedTypeFieldMetadata.getAnnotations().add(createAnnotationMetadataFor((Annotation)parameterizedExtendedModifier));
                } else {
                    Modifier modifier = (Modifier)parameterizedExtendedModifier;
                    parameterizedTypeFieldMetadata.getModifiers().add(new ModifierMetadata(modifier.getKeyword().toString()));
                }
            }
            return parameterizedTypeFieldMetadata;
        }
        if (type.isArrayType()) {
            ArrayType arrayType = (ArrayType)type;
            FieldMetadata arrayTypeFieldMetadata = FieldMetadata.arrayType(getTypeName(arrayType));

            variable = new Variable();
            variable.setName(JavaMetadataUtil.getName(singleVariableDeclaration.getName()));
            arrayTypeFieldMetadata.setName(variable.getName());
            arrayTypeFieldMetadata.getVariables().add(variable);

            for (IExtendedModifier arrayTypeExtendedModifier : (List<IExtendedModifier>)singleVariableDeclaration.modifiers()) {
                if (arrayTypeExtendedModifier.isAnnotation()) {
                    arrayTypeFieldMetadata.getAnnotations().add(createAnnotationMetadataFor((Annotation)arrayTypeExtendedModifier));
                } else {
                    Modifier modifier = (Modifier)arrayTypeExtendedModifier;
                    arrayTypeFieldMetadata.getModifiers().add(new ModifierMetadata(modifier.getKeyword().toString()));
                }
            }
            return arrayTypeFieldMetadata;
        }
        return null;
    }
1209020
public static List<Var> getVarsOfType(List<Var> vars, VarType type) {
        ArrayList<Var> subset = new ArrayList<Var>();
        for (Var v : vars) {
            if (v.getType() == type) {
                subset.add(v);
            }
        }
        return subset;      
    }
530827
def _process_monomial(self, monomial, n_vars):
        
        coeff, monomial = monomial.as_coeff_Mul()
        k = 0
        # Have we seen this monomial before?
        conjugate = False
        try:
            # If yes, then we improve sparsity by reusing the
            # previous variable to denote this entry in the matrix
            k = self.monomial_index[monomial]
        except KeyError:
            # An extra round of substitutions is granted on the conjugate of
            # the monomial if all the variables are Hermitian
            daggered_monomial = \
                apply_substitutions(Dagger(monomial), self.substitutions,
                                    self.pure_substitution_rules)
            try:
                k = self.monomial_index[daggered_monomial]
                conjugate = True
            except KeyError:
                # Otherwise we define a new entry in the associated
                # array recording the monomials, and add an entry in
                # the moment matrix
                k = n_vars + 1
                self.monomial_index[monomial] = k
        if conjugate:
            k = -k
        return k, coeff
1201774
private static BigInteger getMultiChoice(int[] choices, JSchema schema, JSVariant var) throws JMFUninitializedAccessException {
    int choice = choices[var.getIndex()];
    if (choice == -1)
      throw new JMFUninitializedAccessException(schema.getPathName(var));
    BigInteger ans = BigInteger.ZERO;
    // First, add the contribution of the cases less than the present one.
    for (int i = 0; i < choice; i++)
      ans = ans.add(((JSType)var.getCase(i)).getMultiChoiceCount());
    // Now compute the contribution of the actual case.  Get the subvariants dominated by
    // this variant's present case.
    JSVariant[] subVars = var.getDominatedVariants(choice);
    if (subVars == null)
      // There are none: we already have the answer
      return ans;
    return ans.add(getMultiChoice(choices, schema, subVars));
  }
342263
void buildALK(final EncodingResult result, final Variable[] vars, int rhs) {
    final LNGVector<Variable> cardinalityOutvars = this.initializeConstraint(result, vars);
    this.incData = new CCIncrementalData(result, CCConfig.ALK_ENCODER.TOTALIZER, rhs, vars.length, cardinalityOutvars);
    this.toCNF(cardinalityOutvars, rhs, Bound.LOWER);
    assert this.cardinalityInvars.size() == 0;
    for (int i = 0; i < rhs; i++)
      this.result.addClause(cardinalityOutvars.get(i));
  }
493435
public FunctionInputDefBuilder vars( String type, AbstractVarDef... vars)
    {
    for( AbstractVarDef var : vars)
      {
      var.setType( type);
      functionInputDef_.addVarDef( var);
      }
    return this;
    }
1267404
void buildForIncremental(final EncodingResult result, final Variable[] vars, int rhs) {
    cardinalityNetwork.buildAMKForIncremental(result, vars, rhs);
  }