我有一个问题，就是要找到任何数字的2次幂(没有任何幂的数字，如5，将返回null(，幂是和2个整数，当加幂时，返回所述数字。以下是一些例子：
4 -> {2, 2}
5 -> null
6 -> null
7 -> null
8 -> {2, 3}
10 -> null
etc...
尽管我下面的代码可以工作，但它太慢了，当通过这个问题(大约100个整数.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;
}
您的输入不超过2147483647，这意味着只有这么多可能的答案。以下是所有108次幂为5或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
因此，你只需要检查上面列表中的方块、方块和主菜。
一个稍微天真一点的方法是检查所有10个幂2、3、5、7、11、13、17、19、23和29。你不需要检查任何其他的权力，因为它们要么是非素数，要么太大而无法工作。
您可以通过分解一个数字来实现。
设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。。使用二进制搜索可以找到CCD_ 7。这种复杂性CCD_ 8。。。要计算a^b1….u需要log(n(运算。
所以所有二进制运算的复杂性：(log(n) * log log(n))
总配位：log(n) * (log(n) * log log(n))
正如@Mark Dickinson所建议的，对我的代码最有效的更改(在不完全更改它的情况下(是将我的限制限制限制在30，而不是n的2/3，因为任何大于2且幂大于30的数字都会超过Integer.max限制，因此，添加一个额外的表达式(i<30(会大大加快代码的速度，代码将显示在下面。
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;
}