Как найти самый большой квадрат в числе (Java)

Question

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

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

Например,

996 is 2 2 3 83  
1000 is 2 2 2 5 5 5  
100000 is 2 2 2 2 2 5 5 5 5 5 

Моя идея теперь состоит в том, чтобы подсчитать количество вхождений каждого элемента в последовательности, так что если число вхождений делится на два, то это квадрат.

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

Какой самый эффективный способ подсчета событий в ArrayList?Или есть лучший способ найти самую большую площадь?

Answer 1

Наивное решение (грубая сила):

Создайте список квадратов, меньших заданного числа, и затем выполните итерации по этому списку, проверяя, разделяют ли записи данное число.Остановитесь, когда найдете делитель, и это ответ.

Вы также можете настроить это, чтобы генерировать список кандидатов по мере продвижения, а не все сразу.Начните с floor (sqrt (дано)) и уменьшайте, пока не найдете что-то, чей квадрат является делителем.

Что-то более похожее на ваш план:

Фактор числа,постройте карту простых множителей и их кратностей как факторов.

Пройдите по карте и уменьшите все нечетные мультипликаты на один.

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

Answer 2

Нет необходимости создавать массив для этого.Вы можете просто построить квадрат по ходу, как в этом псевдокоде (он же Python):

from math import sqrt

def sqrfact(n):
    lim = sqrt(n) + 1
    x = 2
    while x <= lim:
        if n % x == 0:
            p = n/x
            if p % x == 0:
                return (x ** 2) * sqrfact(p/x)
            else:
                return sqrfact(p)
        x += 1

    # No factors.
    return 1

В зависимости от вводимых вами чисел, это может быть немного быстрее, чем грубая сила.

Answer 3

Обязаны ли вы использовать алгоритм для натуральных чисел?

вы не можете взять квадратный корень из числа и укоротить его?

т.е.= самая большая площадь