So say you are given the numbers 27 and 81. How would a program that tells you that the 4th root of 81 is 3 and the cubic root of 27 is three. (Both have the root of 3).

x = 16;
y = 4;

foo = same_root(16, 4); // foo = 2

root1 = find_root(16, 2); // root1 = 4
root2 = find_root(4, 2); // root2 = 2

CodePudding user response：

You can utilize that simple fact that powers of the same number are divisible by each other. And the product itself is a power of the same root. It means that we can have a simple recursive algorithm as follows:

1. Check if the smaller number divides the larger one.
2. If not - return false (-1 in the code below)
3. If yes, recursively repeat for the smaller number and the product

Our stopping conditions should be when both numbers are equal, but neither is 1, because 1 can't be a common root.

Here is C code implementing this idea (for positive numbers):

#include <stdio.h>

#define TEST(x, y) printf("%d, %d => %d\n", (x), (y), common_root((x),(y)))

int common_root(int a, int b)
{
    int temp;
    
    if (a == 1 || b == 1)
        return -1;
    if (a == b) {
        return a;
    }
    
    if (a > b) {
        // Swap to make sure  a < b
        temp = a;
        a = b;
        b = temp;
    } 
    
    if ( (b % a) == 0) // Check if `b` divisible by `a`
        return common_root(a, b/a);
    else
        return -1;
}

int main(void) {
    TEST(1,2);
    TEST(2,3);
    TEST(6,10);
    TEST(4, 16);
    TEST(12, 24);
    TEST(27, 81);
    return 0;
}

Output:

1, 2 => -1
2, 3 => -1
6, 10 => -1
4, 16 => 4
12, 24 => -1
27, 81 => 3

Demo

CodePudding user response：

Using prime factorization (outlined here), you can make a list of divisors, and then simply check which value(s) are in both lists.