0

I have written a short C++ function which is trying to return similar to the the radical of an integer, but instead the smallest integer which is some root of the the given number. The general logic is that the function decomposes the integer into prime powers, looks for the gcd of all the exponents of the prime powers, then finds the radical by dividing all the exponents by this gcd. I thought the function was working as intended, however I noticed that when passing the function 13 as an argument it returns 12, I have put the output for 2 to 20 below; everything is correct apart from 13. When trying to debug this both "primes" and "powers" hold the correct values (13 and 1 respectively, both vectors of size 1) as well as "power" being 1 as it should. So the problem must be in the last loop, but I am really very confused as to what could be happening as it should be calculating pow(13, 1/1).

#include<vector>
#include<cmath>

int radical(int n){
    int power = 0;
    std::vector<int> primes;
    std::vector<int> powers;
    for(int i = 2; n != 1 ; ++i){
        int t_pow = 0;
        while(n % i == 0){
           ++t_pow;
            n /= i;
        }
        if(t_pow != 0){
            primes.push_back(i);
            powers.push_back(t_pow);
        }
        power = (power == 0 ? t_pow : gcd(power, t_pow));
    }

    int rad = 1;
    for(unsigned i = 0u; i < primes.size(); ++i){
        rad *= pow(primes.at(i), powers.at(i)/power);
    }
    return rad;
}

2 2

3 3

4 2

5 5

6 6

7 7

8 2

9 3

10 10

11 11

12 12

13 12

14 14

15 15

16 2

17 17

18 18

19 19

20 20

EDIT: The most efficient way to implement an integer based power function pow(int, int)

Ben Livingstone
  • 23
  • 6
  • Hmmm, why do you even store the powers? – bipll Jan 08 '18 at 02:02
  • @StPiere integer pow is platform dependent and unsafe in general as pointed out in the question that this duplicates. I have implemented an integer power function as edited into my question – Ben Livingstone Jan 08 '18 at 02:40

2 Answers2

0

The naive algorithm looks pretty simple actually:

rad = 1
i = 1
While n > 1:
    increase i
    if i divides n:
        multiply rad by i
        while i divides n, divide n by i

You're already performing all these steps, the fact is you're doing much more than that (and using much more space), so why not just get rid of unnecessary actions?

bipll
  • 11,747
  • 1
  • 18
  • 32
0

define your own int powi(int,int) function and check if the error petsists

StPiere
  • 4,113
  • 15
  • 24