static int boundedTrialDivision()

in commons-numbers-primes/src/main/java/org/apache/commons/numbers/primes/SmallPrimes.java [171:219]


    static int boundedTrialDivision(int n,
                                    int maxFactor,
                                    List<Integer> factors) {
        final int minFactor = PRIMES_LAST + 2;

        /*
        only trying integers of the form k*m + c, where k >= 0, m is the
        product of some prime numbers which n is required not to contain
        as prime factors, and c is an integer undivisible by all of those
        prime numbers; in other words, skipping multiples of these primes
         */
        final int m = PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES.getValue()
            [PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES.getValue().length - 1] + 1;
        int km = m * (minFactor / m);
        int currentEquivalenceClassIndex = Arrays.binarySearch(
                PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES.getValue(),
                minFactor % m);

        /*
        Since minFactor is the next smallest prime number after the
        first 512 primes, it cannot be a multiple of one of them, therefore,
        the index returned by the above binary search must be non-negative.
         */

        boolean done = false;
        while (!done) {
            // no check is done about n >= f
            final int f = km + PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES.getValue()[currentEquivalenceClassIndex];
            if (f > maxFactor) {
                done = true;
            } else if (0 == n % f) {
                n /= f;
                factors.add(f);
                done = true;
            } else {
                if (currentEquivalenceClassIndex ==
                    PRIME_NUMBERS_AND_COPRIME_EQUIVALENCE_CLASSES.getValue().length - 1) {
                    km += m;
                    currentEquivalenceClassIndex = 0;
                } else {
                    currentEquivalenceClassIndex++;
                }
            }
        }
        if (n != 1) {
            factors.add(n);
        }
        return n;
    }