0

I'm trying to compute the simplest form of the square root of an integer. My Java knowledge is rather limited, but I know many of the basics and such. I can't figure out how to find a simplest form square root given the input of a number to take the square root of.

Ex: User inputs 150, and I take the square root of that in simplest form (5√6).

Quick note: I haven't technically learned arrays and array lists yet so I can't use those for the code.

Connor Eddy
  • 1
  • Are you familiar with Newton's Method for finding roots? This is the typical approach to computing square roots. If you want exact answers that takes a differerent set of tricks -- begin with factoring the integer and finding the perfect squares in the factorization: 150 = 2 * 3 * 5^2. – wcochran Feb 24 '22 at 19:57
  • You can factor the numbers as the previous comment suggests, or if the numbers are small, you can just loop over the squares and test for divisibility. – President James K. Polk Feb 24 '22 at 20:41
  • see [How to get a square root for 32 bit input in one clock cycle only?](https://stackoverflow.com/a/34657972/2521214) – Spektre Feb 25 '22 at 09:53

1 Answers1

1

Simply divide out the all the perfect squares you can. Ideally you would loop over the primes using a precomputed table of primes. The left over number is the portion that is not a perfect square:

    int num = 2*3*3*5*7*7*7*7*11; // 9; // 16; // 150; // input
    int root = 1;
    for (int d = 2; d*d <= num; )
        if ((num % (d*d)) == 0) {  // d^2 divides num
            root *= d;                
            num /= d*d;
        } else {
            d++;
        }
    System.out.println( root + " * sqrt(" + num + ")");

Edited: Thanks to Mark Dickenson's comments.

wcochran
  • 10,089
  • 6
  • 61
  • 69
  • 1
    Does this work if (for example) `num = 16`? It looks as though it would end up giving `2 * sqrt(4)` in that case. (I also suspect that `d*d < num` should be `d*d <= num`, else we'll end up with the wrong answer for an input for `9`.) – Mark Dickinson Feb 25 '22 at 13:55
  • Good calls... let me edit.... – wcochran Feb 25 '22 at 20:09