Помощь Проекта Эйлера (Задача 12) - Основные факторы и тому подобное

Question

Ненавижу спрашивать, но я застрял здесь.

Мне нужно проверить последовательность чисел, чтобы найти первое, которое имеет более 500 факторов: http://projecteuler.net/index.php?section=problems&id=12

-Первый раз я попытался сделать грубый ответ (найдя число с 480 после долгого времени)

-Я сейчас смотрю на определение основных факторов числа и затем использую их, чтобы найти все другие факторы.

В настоящее время я нахожусь на стадии, где я могу получить массив простых факторов для любого числа, которое я ввожу - т. Е. 300 имеет простые факторы 2 2 3 5 5

Используя этот массив основных факторов, я должен иметь возможность рассчитать оставшиеся факторы - это та часть, на которой я застрял. В принципе, насколько я понимаю, мне нужно вычислить ВСЕ возможные комбинации чисел в массиве ...

т.е. 2 * 2
2 * 2 * 3
2 * 2 * 3 * 5
2 * 3
2 * 3 * 3
... и так далее. Но где это становится интересным, с такими вещами, как ... 2 * 5
2 * 3 * 5
... т.е. числа, которые не смежны друг с другом в массиве

Я не могу придумать, как закодировать это в общем виде для любого массива длины ...

Мне нужна помощь! П.С. - Я работаю на Java

РЕДАКТИРОВАТЬ: Мой код перебором - как было предложено, перебор проблемы будет работать, и поэтому в моем коде может быть ошибка: (

package euler.problem12;

public class Solution {

    public static void main(String[] args) {
        int next = 1;
        int triangle = 0;
        int maxFactors = 0;

        while(true) {
            triangle = triangle + next;

            int factors = 1;
            int max = (int) triangle / 2;

            for(int i = 1; i <= max; ++i) {
                if(triangle % i == 0) {
                    factors ++;
                }
            }

            if(factors > maxFactors) {
                maxFactors = factors;

                System.out.println(triangle + "\t" + factors);
            }

            next++;
        }
    }
}

Answer 1

Хорошо, вторая попытка, потому что я слишком усложнял дело.

Ответ дается здесь: http://mathforum.org/library/drmath/view/57151.html

Если вы введете число в простое число коэффициенты мощности, то общее количество факторов определяется путем добавления одного к все показатели и умножения эти результаты вместе. Пример: 108 = 2 ^ 2 * 3 ^ 3, поэтому общее количество коэффициент составляет (2 + 1) * (3 + 1) = 3 * 4 = 12. Конечно, факторы 108 равны 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54 и 108. Это происходит потому, что, чтобы быть фактором, число должно быть одинаковым простых чисел, и возводятся в ту же или низшую степень.

Так что, если вы знаете основные факторы, вам просто нужно сосчитать повторяющиеся и использовать приведенный выше расчет для определения количества факторов.

Answer 2

Насколько я могу судить, в вопросе 12 ничего не говорится о простых числах? Это тот, на кого вы смотрите?

Последовательность номеров треугольников генерируется путем сложения натуральных чисел ...

Если это так, то, возможно, не думать о простых числах поможет? ;)

Answer 3

Возможно, на 3 месяца позже, но здесь идет ...

Я вижу, что второй ответ лишил функцию давать вам требуемый ответ, но в ответ на ваш первоначальный вопрос о том, как вы генерируете все факторы, предполагающие, что вам нужно по какой-то причине, вот как вы это делаете:

Предполагая, что у вас есть факторы в массиве:

int [] primeFactors = new int [] {2, 2, 3, 5, 5};

То, что вам нужно сделать, - это повторять каждую перестановку по порядку для каждой возможной глубины, а затем уменьшать результирующий набор результатов только до уникальных значений.

Я объясню, что я имею в виду: «Перестановка по порядку»: при условии, что вы начинаете с позиции 0 массива, следующий элемент должен быть 1, 2, 3 или 4, если вы начинаете с 1, то следующий должен быть 2, 3 или 4 и т. Д.

«Каждая возможная глубина»: каждый отдельный фактор, затем любые два фактора, затем любые три фактора и так далее, пока не дойдете до всех пяти факторов.

«Уменьшите набор»: если вы берете два элемента, скажем, 0 и 3, 0 и 4, 1 и 3 или 1 и 4, все они дают вам 2 * 5 = 10, все они дают коэффициент 10, поэтому вам нужно сделать так, чтобы ваш набор отличался ценности. (Фу, это становится длиннее, чем я ожидал ...:))

Способ сделать это состоит в том, чтобы использовать два метода: один для выбора максимальной глубины рекурсии, запуска рекуссии и удаления окончательных результатов, а другой для получения значений:

public static void main(String[] args) {
    int[] primeFactors = new int[] {2, 2, 3, 5, 5};
    List<Integer> allFactors = getAllFactors(primeFactors);
    for (int factor : allFactors) {
        System.out.println("Factor: " + factor);
    }
}

private static List<Integer> getAllFactors(int[] primeFactors) {
    Set<Integer> distinctFactors = new HashSet<Integer>();
    for (int maxDepth = 0; maxDepth <= primeFactors.length; maxDepth++) {
        permutatPrimeFactors(0, maxDepth, 0, 1, primeFactors, distinctFactors);
    }
    List<Integer> result = new ArrayList<Integer>(distinctFactors);
    Collections.sort(result);
    return result;
}

private static void permutatPrimeFactors(int depth, int maxDepth, int minIndex, int valueSoFar, int[] primeFactors, Set<Integer> distinctFactors) {
    if (depth == maxDepth) {
        distinctFactors.add(valueSoFar);
        return;
    }

    for (int index = minIndex; index < primeFactors.length; index++) {
        permutatPrimeFactors(depth + 1, maxDepth, index + 1, valueSoFar * primeFactors[index], primeFactors, distinctFactors);
    }
}

getAllFactors использует Set, чтобы убедиться, что мы получаем только отдельные значения, затем добавляет их в список и сортирует их так, чтобы мы могли отображать факторы по порядку.

В то время как permutatPrimeFactors генерирует от нулевых терминов (фактор = 1) до всех терминов (фактор = 1 * 2 * 2 * 3 * 5 * 5 = 300).

Надеюсь, это поможет.