Получите силы идеального числа силы

Question

У меня есть проблема, которая состоит в том, чтобы найти 2 степени любого числа (числа, которые не имеют никаких степеней, такие как 5, вернут ноль), количество степеней и 2 целых числа, которые при добавлении силы возвращают указанное число. Вот несколько примеров:

4 -> {2, 2}
5 -> null 
6 -> null
7 -> null
8 -> {2, 3}
10 -> null
etc...

Хотя мой код, приведенный ниже, работает, однако он слишком медленный, при прохождении через проблему (около 100 значений integer.max) он занимает установленное время (16 секунд), что угодно Я мог бы оптимизировать этот код?

public static int[] isPerfectPower(int n) {  
    int limit = (int)Math.round((n/((double)5/2)));

    for (int i = 2; i <= limit; i++) {  
        double result = Math.pow(n, (double)1/i);   
        result = (double)Math.round(result * Math.pow(10, 10)) /  Math.pow(10, 10);
        if((result == Math.floor(result))) return new int[] {(int)result, i};
    }
    return null;
}

Answer 1

Вы можете сделать это путем разложения числа.

Позволяет n = p1^k1 * p2^k2 * p3^k3, где p1, p2, p3 = простое число.

Тогда число будет совершенной степенью, если gcd(k1, k2, k3) != 1 ( У них должен быть общий делитель) ..

Пример:

2500 = 2^2 * 5^4
     = 2^2 * (5^2)^2
     = 2^2 * 25^2
     = 50^2

Таким образом, вы можете рассчитать мощность совершенных сил.

Способ 2:

Позволяет n = a^b ... вам нужно найти a & b где b < log(n) ...

Теперь вам нужно найти a .. вы можете найти a используя бинарный поиск. эта сложность log(a) ... для вычисления ^ b1 ..... вам нужна операция log (n).

Итак, сложность для всех двоичных операций: (log(n) * log log(n))

Всего сложностей : log(n) * (log(n) * log log(n))

Answer 2

Как предложил @Mark Dickinson, наиболее эффективным изменением в моем коде (без его полного изменения) было бы ограничение моего значения 30 вместо 2/3 от n, так как любое число> 2 со степенью больше 30 будет превышение предела Integer.max, поэтому добавление дополнительного выражения (i <30) значительно ускорит код, код будет отображаться ниже. </p>

      public static int[] isPerfectPower(int n) {
        for(int i = 2; i <= ((n < 30) ? n : 30) && i < 30; i++) {
            double result = (double)Math.round(Math.pow(n, (double)1/i) * Math.pow(10, 10)) /  Math.pow(10, 10);
            if((result == Math.floor(result))) return new int[] {(int)result, i};
        }
        return null;
      }

Answer 3

Ваш ввод не более 2147483647, что означает, что есть только так много возможных ответов. Вот упорядоченный список всех 108 совершенных способностей, с силой 5 или более.

2**5, 2**7, 3**5, 4**5, 2**11, 3**7, 5**5, 6**5, 2**13, 4**7, 7**5, 8**5, 9**5, 5**7, 10**5, 2**17, 11**5, 3**11, 12**5, 6**7, 13**5, 2**19, 14**5, 15**5, 7**7, 16**5, 17**5, 3**13, 18**5, 8**7, 19**5, 20**5, 21**5, 4**11, 9**7, 22**5, 23**5, 24**5, 2**23, 25**5, 10**7, 26**5, 27**5, 28**5, 11**7, 29**5, 30**5, 31**5, 32**5, 12**7, 33**5, 34**5, 5**11, 35**5, 36**5, 13**7, 4**13, 37**5, 38**5, 39**5, 40**5, 14**7, 41**5, 3**17, 42**5, 43**5, 44**5, 15**7, 45**5, 46**5, 47**5, 48**5, 16**7, 49**5, 50**5, 51**5, 6**11, 52**5, 17**7, 53**5, 54**5, 55**5, 2**29, 56**5, 57**5, 18**7, 58**5, 59**5, 60**5, 61**5, 19**7, 62**5, 63**5, 64**5, 65**5, 3**19, 5**13, 66**5, 20**7, 67**5, 68**5, 69**5, 70**5, 21**7, 71**5, 72**5, 7**11, 73**5

Поэтому вам нужно только проверить наличие квадратов, кубов и входов в списке выше.

Немного более наивным методом было бы проверить все десять степеней 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Вам не нужно проверять какие-либо другие полномочия, так как они не являются -прайм или слишком большой, чтобы когда-либо работать.