获得一个完美的幂数的幂 [英] Get powers of a perfect power number

问题描述

我有一个问题，就是要找到任意数量的2个幂(没有任何幂的数字，例如5将返回null)，幂为和2个整数，将它们相加后会返回该数字.以下是一些示例:

I have a problem which is to find the 2 powers of any number (numbers that don't have any powers such as 5 will return null), powers being and 2 integer numbers that when added power to return the said number. Here are some examples:

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

尽管下面的代码可以工作，但是它太慢了，但是当遇到问题(大约100个integer.max值)时，它花费了设置的时间(16秒)，我有什么可以优化此代码的呢?

Although my code below works, however its too slow, when passed through the problem (about 100 integer.max values) it takes over the set time (16 seconds), anything I could to optimize this code?

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;
}

推荐答案

您输入的内容不超过2147483647，这意味着答案可能太多.这是所有108个5或5以上的完美力量的有序列表.

Your input is no more than 2147483647, which means there are only so many possible answers. Here is an ordered list of all 108 perfect powers with a power of 5 or more.

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

因此，您只需要检查上面列表中的正方形，立方体和主角即可.

Therefore you only have to check for squares, cubes, and entrees of the list above.

一种比较幼稚的方法是检查所有10个幂2、3、5、7、11、13、17、19、23和29.您不需要检查任何其他幂，因为它们都是非质数或太大而无法正常工作.

A slightly more naïve method would be to check all ten powers 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. You do not need to check any other powers, as they are either non-prime or too large to ever work.

这篇关于获得一个完美的幂数的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！