How to find the largest square in the number (Java)

I want to decompose the number into the product of the largest square in this number and some other number, but I am stuck at some point. I would really appreciate some suggestions. This is what I've done so far:

I take the number on the input, factorize into prime numbers, and put the sequence of prime numbers to ArrayList. Numbers are sorted, in a sense, thus the numbers in the sequence are increasing.

For example,

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 

My idea now is to c开发者_StackOverflowount number of occurrences of each elements in the sequence, so if the number of occurrences is divisible by two, then this is the square.

In this way, I can get another sequence, where the right most element divisible by two is the largest square.

What is the most efficient way to count occurrences in the ArrayList? Or is there any better way to find the largest square?

---

Naive (brute force) solution:

Generate a list of a squares less than the given number, and then iterate down this list checking if the entries divide the given number. Stop when you find a divisor and it's the answer.

You could also adjust this to generate the list of candidates as you go rather than all at once. Start with floor(sqrt(given)) and decrement until you find something whose square is a divisor.

Something more resembling your plan:

Factor the number, and build a map of prime factors and their multiplicities as factors.

Go through the map and reduce all odd multiplicites by one.

Multiply all the numbers in the map raised to the adjusted multiplicities.

---

It is not necessary to build an array to do this. You can just build up the square as you go, as in this pseudocode (aka 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

Depending on the types of number you input, this may be slightly faster than brute force.

---

Are you obligated to use an algorithm on natural numbers?

cant you take the square root of the number and truncate it down?

ie trunc( squareRoot(10001)) = 100 = largest square