怎样判断一个整数是不是幂的形式
如9 ＝ 3^2
125 = 5^3
即可以表示成a的b次方的形式（a,b为整数，b>1)
问题点数：50、回复次数：48Top
1 楼NowCan（城市浪人）回复于 2006-08-07 12:29:00 得分 0
做因数分解，如果因数只有一种，那就是了。Top
2 楼yyfhz（火山）回复于 2006-08-07 13:17:28 得分 0
做因数分解，如果各个不同的素因子之间有公约数，那就是了Top
3 楼yelling（Ray（←☆→射手））回复于 2006-08-08 09:51:16 得分 0
不需要因数分解，只需求得第一个最小因子，再去不断求商就可以判断。Top
4 楼yyfhz（火山）回复于 2006-08-08 10:36:04 得分 0
to yelling(Ray（←☆→射手）)
怎样通过"对最小因子的不断求商"来判断？这样做的结果会不会就是一个因子分解?Top
5 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-08 10:59:40 得分 0
不需要因数分解，只需求得第一个最小因子，再去不断求商就可以判断。
========
那 36=(2*3)^2 符不符合呢？
判断是否为整数幂需要一些数论知识，尤其是对超大整数检测时。Top
6 楼bacmoz（）回复于 2006-08-08 11:07:27 得分 0
不需要这个算法了，不过讨论一下还是很有意思的Top
7 楼mmmcd（超超）回复于 2006-08-13 09:51:08 得分 0
topcoder见过这个问题。
直接枚举指数（长整型不超过31）
x=31;x>1;x--
a=(int)pow(n,1.0/x)
a连乘x次,若等于n,就是Top
8 楼bigc2000（公元2005年4月9日）回复于 2006-08-16 11:22:15 得分 0
我来了，赶快揭帖！
如下解决：
先因素分解；将所得到的每个质数记录下来
然后判断每个质数的个数，
[原理]在所有质数中，其中质数最少出现的次数必定是幂指数。判断其他质数的次数是不是该质数c出现次数的整数倍。
A ={某个质数N出现的次数最少} N= 该质数
如果满足它的次数 A〉1，并且其他质数（如果有）的次数是该质数N出现次数A的整数倍
18=2*3*3 不是，因为2出现的次数==1
25 = 5*5 是5出现的次数为2
125 = 5*5*5 是5出现的次数为3
36 =2 *2 *3 *3; 因为质数2出现次数为2，3出现的次是是他的1倍
36*25 = 2*2*3*3*5*5*5*5 -----------2出现次数最少，3，出现次数是他的1倍，5 是2倍Top
9 楼yelling（Ray（←☆→射手））回复于 2006-08-16 18:12:58 得分 0
楼上效率很低。超超的方法应是正解Top
10 楼shshsh_0510（雨下了4年11个月零2天）回复于 2006-08-17 13:09:41 得分 0
double l,X,t;
l = lg(n);
X= exp(n,0.5);
for( i=1; i< X ;i++)
{
t=l/lg(i);
if( t-floor(t)<0.00000001) //A_VERY_SMALL_NUMBER
{
//may be
return test(i,n)
}
}
Top
11 楼kingkiosk（）回复于 2006-08-18 09:56:03 得分 0
穷举就行了,数就算再大,用幂的形式也就没什么了~
算法思路是:由y=2开始,每个数由2次方,3次方一直乘方到大于接收的数,然后再让y自加1,重新从2次放开始检测,直到y的平方大于S为止
lend(double s)
{double x,y=2,z=1;
int n=2;
while(y*y<=s) //如果y的平方小于S,则证明S不是任何数的N次幂
{x=y;
while(x<s)
{x=x*y //每次都乘一个基数
if(x==s) return y; //如果相等,则返回,返回后通过Y的值就能计算出次幂
n++;
}
y++; //y自增1
}
return 0; //如果整个循环都走完了,则这个数不是幂的形式
}
大家不要忘了,计算机的优势就是运算速度快.可以做重复的劳动,穷举在很多时候都适用的.Top
12 楼spirit_sheng（老盛）回复于 2006-08-18 17:43:03 得分 0
如果用超超类似的思想, 则只用判断幂是质数的情况
如果是 32 位或 64 位整数, 这都容易, 但如果是大整数, 大家可以讨论一下该怎么处理
Top
13 楼kingkiosk（）回复于 2006-08-20 11:07:57 得分 0
楼上的你有什么思路或者想法吗?Top
14 楼kingkiosk（）回复于 2006-08-20 11:10:12 得分 0
幂是因数的用穷举也能出来,例如 144=12^2 12本身就不是质数Top
15 楼yyfhz（火山）回复于 2006-08-21 11:35:51 得分 0
To LZ:
数字 3*3*3*3*5*5*5*5*5*5 由4个3和6个5连乘组成
它应当是(3*3*5*5*5)的2次方。
不过按照LZ的方法似乎得不出这个结论Top
16 楼yyfhz（火山）回复于 2006-08-21 11:37:51 得分 0
说错了，应该是
To bigc2000(公元2005年4月9日)
数字 3*3*3*3*5*5*5*5*5*5 由4个3和6个5连乘组成
它应当是(3*3*5*5*5)的2次方。
Top
17 楼chenmaosheng（）回复于 2006-08-22 10:35:40 得分 0
超超的方法不错，我用107的3次方，也就是1225043，算了10万次，需要1188毫秒，但是他的方法是基于计算机的整数而不是所有整数。
我的方法是这样的：
int sum = 1225043;
int large = sqrt((float)sum);
float sum_in_float = (float)sum;
for (int i = 2; i < large; ++i)
{
a = sum_in_float / i;
if (a - (int)a < 0.0001)
{
flag = true;
break;
}
}
if (flag)
{
while (true)
{
sum_in_float = sum_in_float / a;
if (fabs(sum_in_float - a) < 0.0001)
{
//std::cout <<"OK";
break;
}
if (sum_in_float < a)
{
//std::cout <<"False";
break;
}
}
}
这个方法在和超超的相同运算中只花了657毫秒，而如果整数改为65536的话，它只需要31毫秒，远远快于超超方法算65536的656毫秒。
欢迎大家提点，谢谢！Top
18 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-22 13:15:40 得分 30
to 楼上：这是因为CPU整数运算远快于浮点运算。
如果判定一个32bits无符号变量是否为指数不小于2的整数幂，
下面的算法也许会比较快（这是我突然想到的）。
显然0和1满足要求（当然，你也可以定义它不满足要求）。
下面讨论的范围将限于：[2, 2^32-1]。
因为：n^(p*q)=(n^p)^q (n、p、q为正整数，"^"为乘方运算)，
所以我们仅需判定它是否为：2,3,5,7,11,13,17,19,23,29,31 整数次方即可
k^31 型的整数仅1个：2^31
k^29 型的整数仅1个：2^29
k^23 型的整数仅1个：2^23
k^19 型的整数仅2个：2^19 和 3^19
k^17 型的整数仅2个：2^17 和 3^17
k^13 型的整数仅4个：2^13、3^13、4^13、5^13
。。。
k^7 型的整数仅22个：2^7、3^7、。。。、23^7
我们可将上述数字写入一数组并排序（共 39 个数），
通过二分法查找即可判定它是否为 7,11,13,17,19,23,29,31 整数次方。
现尚余“是否为 2,3,5,7 整数次方？”需判定，
为避免浮点开方运算，可以通过牛顿迭代快速计算，
初始值的设定也有讲究（以加快收敛），
可通过欲判定数的bits数（用汇编指令可迅速获得）及开方数进行预估。
好了，这是我的想法，欢迎大家指正。Top
19 楼chenmaosheng（）回复于 2006-08-22 13:48:53 得分 0
楼上的老兄，我说过啦，整数可不一定是32位的哦。Top
20 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-22 14:28:50 得分 0
看样子，chenmaosheng() 也并没有留意我事先的申明：“下面讨论的范围将限于：[2, 2^32-1]”
不同的范围应对应不同的算法。
小范围查表遍历可能最快；大的范围则需用更好的算法。
但我始终不认为：原本是整数判定的问题，采用浮点乘除、开方的算法效率能最佳，
也许其代码会很简洁，但效率却会大打折扣。
假如是超大整数，仅一个“是否为完全平方数”的问题就大有学问，
而这决不能通过循环试探的方法解决，否则不知要到猴年马月去了。Top
21 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-22 14:55:28 得分 0
要想快速判定，必需一些数论知识。
比如说，对于单偶数（不被4整除的偶数）就无需判定直接可以“咔嚓”了！Top
22 楼bigc2000（公元2005年4月9日）回复于 2006-08-22 23:33:19 得分 0
我原来的方法确实错了。
不好意思，数轮没有学过。但我又想了想，觉得下面这个应该可行。
所有质因数的个数构成的集合A{a1，a2，。。。}
而集合A中元素a1，a2，a3最大公约数s
如果s>1，那么N就是幂数。
比如果
2*2*2*2*3*3*3*3*3*3*3 质因数个数的集合{4，6}最大公约数为2〉1所以是幂数
5*5*5 质因数个数的集合{3}最大公约数为3〉1所以是幂数
Top
23 楼bigc2000（公元2005年4月9日）回复于 2006-08-22 23:46:50 得分 0
写错了2*2*2*2*3*3*3*3*3*3 他的质因数个数组成的集合为{4，6}
我是这样分析的，请大虾们所说看看。
因为质因数个数的最大公约数为s
那么队以任意质因数 pi，它出现的次数为ai；
必有ai %s = 0，所以一定能够将该质因数pi 分成s组，每组ai/s个。他的积为pi^(ai/s)
这样就将将所有质因数都分成了s组
原数N= {pi^(ai/s)} ^s,所以幂指数为s，底数为 pi^(ai/s)之积 注 i-1，2，3,...
Top
24 楼yyfhz（火山）回复于 2006-08-24 11:49:27 得分 0
这个想法好像是没有问题了。至于效率上是否可以...那是另外一个问题了。
当然在判断的时候，只要发现2个不同的质因数的个数没有公约数的话，就可以判断说它不是幂指数的数字了，不过对于那些可以表示成幂指数的数字来讲..还得一个一个算到底。Top
25 楼bigc2000（公元2005年4月9日）回复于 2006-08-24 17:13:50 得分 0
To yyfhz(火山) ( ) 信誉：100 Blog 2006-08-24 11:49:00 得分: 0
这个想法好像是没有问题了。至于效率上是否可以...那是另外一个问题了。
当然在判断的时候，只要发现2个不同的质因数的个数没有公约数的话，就可以判断说它不是幂指数的数字了，不过对于那些可以表示成幂指数的数字来讲..还得一个一个算到底。
-----------------------------------------------------------------------------
我觉得首先要求算法是正确的是一切的关键。这个效率还是很高的，这个我考虑过,计算方法如下java写的，其实还可以优化查找最大公约数，
public class PowerExponent {
int currentGreatestCommonDivisor = 0;//记录计算时当前质因子个数 之间的最大的公约数初始化为0表示不可用
int currentPrimerDivisorCount =0 ; //用于记录当前质因素 个数计数
int prePrimerDivisorCount =0;//前一个质因数计数个数
int currentPrimerDivisor =0; //先前质因子
public void setCurrentGreatestCommonDivisor(int value)
{
this.currentGreatestCommonDivisor = value;
}
public int getCurrentGreatestCommonDivisor()
{
return this.currentGreatestCommonDivisor ;
}
public boolean isPowerExponentNumber(final int orignNumber)
{
int number =orignNumber;
prePrimerDivisorCount =0;
currentPrimerDivisor =0;
currentGreatestCommonDivisor = 0;//初始化为0表示不可用
currentPrimerDivisorCount = 0;
if(number>3)
{
currentPrimerDivisor = 2;
while(number%2 == 0)
{
number /= 2;
++currentPrimerDivisorCount;
}
int i = 3;
while(number >=i )
{
while(number%i == 0)
{
if(i == currentPrimerDivisor)
{
++currentPrimerDivisorCount;
}
else
{
//新的质因素开始，计数个数设置为1 ,统计前一个质数的个数,记录当前质因子
prePrimerDivisorCount = currentPrimerDivisorCount;
currentPrimerDivisor = i;
currentPrimerDivisorCount = 1;
//判断最大公约数
if(currentGreatestCommonDivisor != 0)
{
//如果最大公约数！=0表明一定不是第一次求最大公约数
currentGreatestCommonDivisor = PowerExponent.FindGreatestCommonDivisor(currentGreatestCommonDivisor,prePrimerDivisorCount);
if(currentGreatestCommonDivisor == 1)
{
return false;
}
}
else
{
currentGreatestCommonDivisor = prePrimerDivisorCount;
if(currentGreatestCommonDivisor == 1)
{
return false;
}
}
}
number /=i;
}
if(i>(int)Math.sqrt(orignNumber))
{
//存在一个比它开方还大的质因子所以必非幂数
return false;
}
i+=2;
}
//质因素分解结束 number == 1
if(currentGreatestCommonDivisor == 0 && currentPrimerDivisorCount >1 ||prePrimerDivisorCount ==0)
{
//只有一个质因子
return true;
}
else
{
//求所有质因子个数的 最大公约数
currentGreatestCommonDivisor = PowerExponent.FindGreatestCommonDivisor(currentGreatestCommonDivisor,currentPrimerDivisorCount);
if(currentGreatestCommonDivisor == 1)
{
return false;
}
else return true;
}
}
return false;
}
/**
*
* @param a a>0
* @param b b>0
* @return 最大质因素
*/
public static int FindGreatestCommonDivisor(final int orignNumber_a,final int orignNumber_b)
{
int a= orignNumber_a;
int b= orignNumber_b;
if(a==1 || b== 1) return 1;//互质
if( a%b == 0 )
{
return b;
}
if(b%a == 0)
{
return a;
}
int product =1 ;
int greatesCommonDivisor = 1;
while(a%2 == 0&& b%2 ==0)
{
a /= 2;
b /=2;
product *=2;
}
int i = 3;
while(a>=i&&b>=i)
{
while(a%i == 0 && b%i ==0)
{
a /= i;
b /= i;
product *=i;
}
if(i > (int)Math.sqrt(orignNumber_a) || i > (int)Math.sqrt(orignNumber_b))
{
//当前的a ，b存在一个比它开方还大的质因子所以没有必要再分解质因子
greatesCommonDivisor = product;
return greatesCommonDivisor;
}
i += 2;
}
greatesCommonDivisor = product;
return greatesCommonDivisor;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
PowerExponent pe = new PowerExponent();
boolean bRet = false;
long startMills = System.currentTimeMillis();
// for(int i=Integer.MAX_VALUE -100000;i<Integer.MAX_VALUE;i++)
// {
// bRet = pe.isPowerExponentNumber(i);
// //System.out.println(i+"是幂指数吗?"+bRet);
// if(bRet)
// {
// System.out.println(i+"是幂指数");
// }
// }
bRet = pe.isPowerExponentNumber(2147395600);
if(bRet)
{
System.out.println(2147395600+"是幂指数");
}
bRet = pe.isPowerExponentNumber(2*2*2*2*3*3*3*3*3*3*5*5*5*5*7*7);
System.out.println(2*2*2*2*3*3*3*3*3*3*5*5*5*5*7*7+"=2*2*2*2*3*3*3*3*3*3*5*5*5*5*7*7"+"是幂指数吗"+bRet);
long endMills = System.currentTimeMillis();
System.out.println("耗时"+(endMills - startMills));
}
}
我做过测试 10w个最大的数字，只需要3182ms（main中注释去掉就可以了）
程序是否正确，也请诸位验证下，目前本人测试了从1-256都正确Top
26 楼bigc2000（公元2005年4月9日）回复于 2006-08-24 17:19:18 得分 0
我觉得诸位测试的数据太小了都没有到达10亿以上的数据。这样是难以说服其复杂度的Top
27 楼bigc2000（公元2005年4月9日）回复于 2006-08-24 17:39:25 得分 0
真不好意思，复制了一个旧版本，新的修改了sqrt函数
i>(int)Math.sqrt(orignNumber)) 替换成 i*i > orignNumber
把
i > (int)Math.sqrt(orignNumber_a) || i > (int)Math.sqrt(orignNumber_b))
替换成
i*i > orignNumber_a || i *i > orignNumber_b
速度在最坏情况下改善了不少。
if(currentGreatestCommonDivisor == 0 && currentPrimerDivisorCount >1 ||prePrimerDivisorCount ==0)
把这句替换成
if(currentGreatestCommonDivisor == 0 && currentPrimerDivisorCount >1 )
这个 || 是不对的，虽然结果对，但不合逻辑，而且也需要多判断一次。谢谢。
Top
28 楼mmmcd（超超）回复于 2006-08-25 11:28:30 得分 0
呵呵
虽然楼主说“不需要这个算法了”，讨论一下确实很有意思。
如果输入长达1万位的整数，判断一下是否幂的形式？
Top
29 楼yyfhz（火山）回复于 2006-08-25 16:04:24 得分 0
的确，这是个挺有趣的问题。如果这样的话，计算10000位数的+,-,*,/是一个很麻烦的事情。Top
30 楼bigc2000（公元2005年4月9日）回复于 2006-08-25 18:15:15 得分 20
mmmcd(超超) ( ) 信誉：124 Blog 2006-08-25 11:28:00 得分: 0
呵呵
虽然楼主说“不需要这个算法了”，讨论一下确实很有意思。
如果输入长达1万位的整数，判断一下是否幂的形式？
-------------------
这就不好说了，不知道那位数学家能够写出幂数的通式！恐怕这个是最重要的，也就是方法是关键，至于效率可以改进
还有我发现我的方法（今天我有改进了些）比你说的要快好多倍
gxqcn(★) HugeCalc ← http://maths.diy.myrice.com/ (☆) ( ) 信誉：100 Blog
你的算法我不太明白（我很愚钝），写出算法来，我来看看速度就可以了
讨论这个确实有点意思
我又选了最小的数字 1--64000 总共花时间63ms(我机器512M，赛扬D2.4G）
Top
31 楼mmmcd（超超）回复于 2006-08-25 18:51:42 得分 0
topcoder的SRM305这道题：
Problem Statement for PowerCollector
Problem Statement
Your friends collect butterflies and stamps, but you collect numbers. Your collection of prime numbers is the finest in three counties, and your collection of transcendental numbers has been featured on national talkshows. Lately you've decided to start collecting powers, that is, numbers that can be written in the form MK, where M and K are positive integers with K > 1. However, you're wondering how big a box you'll need to hold them all. Given a number N, represented as a String, determine how many powers lie between 1 and N, inclusive. Return the number of powers as a String with no leading zeros.
Definition
Class: PowerCollector
Method: countPowers
Parameters: String
Returns: String
Method signature: String countPowers(String N)
(be sure your method is public)
Constraints
- N will contain between 1 and 19 characters, inclusive.
- Each character in N will be a digit ('0'-'9').
- The first character in N will not be zero ('0').
- N will represent a number between 1 and 1000000000000000000 (10^18), inclusive.
Examples
0)
"10"
Returns: "4"
The powers between 1 and 10 are 1, 4, 8, and 9.
1)
"36"
Returns: "9"
The powers between 1 and 36 are 1, 4, 8, 9, 16, 25, 27, 32, and 36.
2)
"1000000000000000000"
Returns: "1001003332"
输入N,统计1～N之间多少个整数是幂的形式
N最大10的18次方Top
32 楼mmmcd（超超）回复于 2006-08-25 18:54:39 得分 0
做枚举的话，枚举指数效率要远高于枚举底数。
如果数太小就没可比性，
就像快速排序在元素少时效率可能比冒泡排序低。Top
33 楼yuxh（yuxh）回复于 2006-08-26 08:39:00 得分 0
我写的一个十进制数运算类，ispow()判断是否是整数次幂
http://www.cublog.cn/u/2882/
Top
34 楼bigc2000（公元2005年4月9日）回复于 2006-08-26 14:49:49 得分 0
Tp mmmcd(超超) ( ) 信誉：124 Blog 2006-08-25 18:54:00 得分: 0
不知道您那个时间是多少！
int java中 最大只能是2^31-1，对于任意个int大数时间不超过16ms。
做枚举的话，枚举指数效率要远高于枚举底数。
可是，这个不正确的，比如幂数N = M^2，N是个很大的数，M也不小，这必然要枚举底数
而且如果从小数枚举的时间不少，
按照你的说法，这样的程序
采用 从大到小来枚举，比如你的程序（不知道我理解的对不对）
int i = 0;
e =2;
do{
i = (int)extract(N,e);//开方运算将N开e次方,转化为int型
if(i <= 1) return false;
if(pow(i,e) == N)
{
return true;
}
else
e++;
}
上面是指数从小到大枚举（从大到小也可以，结果也差不多），可是有个问题，如果是2^N（最坏情况），收敛速度是比较快的
但有个问题，浮点数开方运算远比 加法运算和乘法，除法整数运算，慢很多。所以我得出，效率比你提供算法高的结论。像65536以内的所有数字，所用时间均显示为0ms
当然的确像你说的如果是1w位，或许你的算法更快。我没法去测试（我喜欢用java）。Top
35 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-26 15:00:32 得分 0
对于任意个int大数时间不超过16ms。
================================
知道16ms的概念吗？
我可以用它完成10000!的精确计算；
或者搜索并输出 12000000 以内的所有素数(788060个素数)！
n^x 远比 x^n 增长得快，所以 mmmcd(超超)所言“枚举指数效率要远高于枚举底数”是合理的。Top
36 楼bacmoz（）回复于 2006-08-26 15:26:05 得分 0
感谢大家讨论，我这个算法本来是作为预判断使用的，如果不是幂的形式就进行下一步的计算
如果复杂度稍高一点就没有意义了（因为本来幂形式的数就不多，因此减少的运算量可能就不太大）
复杂度高一点点，对整个过程都很有影响，因为几乎对每个数字（范围之内的）都要判断
后来我不采用这种方法了Top
37 楼bigc2000（公元2005年4月9日）回复于 2006-08-26 15:38:52 得分 0
知道16ms的概念吗？
我可以用它完成10000!的精确计算；
或者搜索并输出 12000000 以内的所有素数(788060个素数)！
------------------------
谢谢你的回复，请将你的代码写出来，我来测试下先，第一我是用java程序写的，如果你用c
我会改成相应c，第二，我是在debug条件下的，而不是release。Top
38 楼bigc2000（公元2005年4月9日）回复于 2006-08-27 00:57:32 得分 0
做人要厚道！Top
39 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-27 15:34:54 得分 0
to bigc2000(公元2005年4月9日):
看样子，我再不给出代码就被人称为“不厚道”了。
阁下既会java又会c，比我强多了（我就会c）；希望能看到你公正的对比测试报告。
// 快速判定一个 UINT32 类型的整数是否为整数次幂
// gxqcn@163.com（2006-08-27）
#include <stdio.h>
typedef unsigned int UINT32;
typedef long BOOL;
#define TRUE 1;
#define FALSE 0;
const UINT32 Pow2( const UINT32 u32Base )
{
return u32Base * u32Base;
}
const UINT32 Pow3( const UINT32 u32Base )
{
return u32Base * u32Base * u32Base;
}
const UINT32 Pow5( const UINT32 u32Base )
{
const UINT32 u32Square = u32Base * u32Base;
return u32Square * u32Square * u32Base;
}
typedef const UINT32 (*fnPow)( const UINT32 );
const BOOL IsPower( const UINT32 u32Num, const UINT32 u32Exp/* 2, 3, or 5 */ )
{
UINT32 u32Pow;
UINT32 u32Root;
UINT32 u32Try;
UINT32 u32Max;
UINT32 u32Min;
fnPow pfnPow;
switch( u32Exp )
{
case 2:
u32Min = 1UL;
u32Max = 65536UL;
pfnPow = Pow2;
break;
case 3:
u32Min = 1UL;
u32Max = 1626UL;
pfnPow = Pow3;
break;
case 5:
u32Min = 1UL;
u32Max = 85UL;
pfnPow = Pow5;
break;
default:
return FALSE;
}
do
{
u32Try = (( u32Max + u32Min ) >> 1 );
u32Pow = ( *pfnPow )( u32Root = u32Try );
if ( u32Num > u32Pow )
{
u32Min = u32Try;
}
else if ( u32Num < u32Pow )
{
u32Max = u32Try;
}
else if ( u32Num == u32Pow )
{
return TRUE;
}
u32Try = (( u32Max + u32Min ) >> 1 );
} while( u32Root != u32Try );
return FALSE;
}
int main(int argc, char* argv[])
{
UINT32 u32Num;
UINT32 u32RShift;
UINT32 u32Odd;
BOOL bIsPower;
do
{
printf( "\nn = " );
scanf( "%u", &u32Num );
_asm
{
mov eax, u32Num
bsf eax, eax
mov [u32RShift], eax
}
u32Odd = u32Num >> u32RShift;
bIsPower = ( 1 >= u32Odd );
while ( !bIsPower )
{
if ( 1162261467UL /* 3^19 */ == u32Odd \
|| 129140163UL /* 3^17 */ == u32Odd \
|| 1220703125UL /* 5^13 */ == u32Odd \
|| 1594323UL /* 3^13 */ == u32Odd \
|| 1977326743UL /* 7^11 */ == u32Odd \
|| 48828125UL /* 5^11 */ == u32Odd \
|| 3404825447UL /* 23^7 */ == u32Odd \
|| 1801088541UL /* 21^7 */ == u32Odd \
|| 893871739UL /* 19^7 */ == u32Odd \
|| 410338673UL /* 17^7 */ == u32Odd \
|| 170859375UL /* 15^7 */ == u32Odd \
|| 62748517UL /* 13^7 */ == u32Odd )
{
bIsPower = ( 0 == u32RShift );
break;
}
if ( 177147UL /* 3^11 */ == u32Odd )
{
bIsPower = ( 0 == u32RShift || 11 == u32RShift );
break;
}
if ( 19487171UL /* 11^7 */ == u32Odd \
|| 4782969UL /* 9^7 */ == u32Odd \
|| 823543UL /* 7^7 */ == u32Odd )
{
bIsPower = ( 0 == u32RShift || 7 == u32RShift );
break;
}
if ( 78125UL /* 5^7 */ == u32Odd \
|| 2187UL /* 3^7 */ == u32Odd )
{
bIsPower = ( 0 == u32RShift || 7 == u32RShift || 14 == u32RShift );
break;
}
if ( 0 == ( u32RShift % 2 ) && 1 == ( 7 & u32Odd ) && IsPower( u32Odd, 2 ))
{
bIsPower = TRUE;
break;
}
if ( 0 == ( u32RShift % 3 ) && IsPower( u32Odd, 3 ))
{
bIsPower = TRUE;
break;
}
if ( 0 == ( u32RShift % 5 ) && IsPower( u32Odd, 5 ))
{
bIsPower = TRUE;
break;
}
break;
}
if ( bIsPower )
{
printf( "%u is a perfect power!\n", u32Num );
}
else
{
printf( "%u is not a perfect power!\n", u32Num );
}
} while( 0 != u32Num );
return 0;
}
/* 附记：
1、本算法是根据特定的判定对象定制的，不具备普适性；
2、本算法全部为整型运算，未调用任何浮点指令；
3、本算法中少量取余还可以进一步优化；IsPower() 函数还可进一步优化，或可采用 Newton's iteration
*/
另外，如果仅是统计某范围内“perfect power”的数目，可先计算各素数指数时可取的最大底数，而后通过容斥原理可快速算得。Top
40 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-27 15:42:21 得分 0
请将 IsPower() 函数中的第一个“u32Try = (( u32Max + u32Min ) >> 1 );”移到“do”前。Top
41 楼bigc2000（公元2005年4月9日）回复于 2006-08-27 22:27:58 得分 0
刚看了下，实在佩服！连汇编都用上了。把它copy下来来看看。不过，我好像没有搞清楚
我说得16ms问题是1000！（无关紧要了）.只是你这个程序与我的思路没有多大的区别，我是把数字 N = N/质数i;不断迭代下去，每次都与前面出现的质素次数的最大公约数，如果为1就为false。
这个，我想你的速度应该要快些，但不是因为算法的缘故，而是你用的是静态算法，即你先目测了一些质数，和可能的最大指数，换句话说，如果我预先得到一些可能质素，那么我的算法次数更少（但可能有除法而慢一些）
最坏情况是做了log2（N）次除法和取余，或者{查找到可能为N的开方根的最大质素所需要的次数}的这么多次取余算法。当然找到质素的开销没有算在内。
最好情况是一次除法，二次取余。比如N被6整除，但不能被4整除的任何数。
对于任意给定的N，我计算的最大复杂性最坏情况主要集中在查找N的开方以内的质素。所以说我枚举底数，比如说是查找质素。希望你也分析下你得先。
还有你的算法与你所的枚举指数 好像并没有多大关系
谢谢你的回复，不用称我为阁下。我copy你写的代码先Top
42 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-28 10:02:20 得分 0
为叙述方便，定义“k|n”为“整数n可以被整数k整除”；“^”表示乘幂。
Input: u32Num ( 0 <= n < 2^32 )
Output: TRUE/FLASE - u32Num 是否可以表示成 k^r 形式( k、r∈N，r≥2 )
1、令 u32Odd、u32RShift，使得 u32Num = ( 2^u32RShift ) * u32Odd，其中 u32Odd 为 0 或 一奇数;
2、if u32Odd <= 1 then return TRUE;（要么为“0”，要么为 2^u32RShift）
3、判定是否可表示成 k^r 型，其中 r = 31, 29, 23, 19, 17, 13, 11, 7 之一，显然此时的前提条件是 u32Odd 是否为 k^r 型；
由于 r 较大，所以仅用比较，遍历一个size=18的数组即可完成：
3.1 { 3^19、3^17、5^13、3^13、7^11、5^11、23^7、21^7、19^7、17^7、15^7、13^7 }
3.2 { 3^11 }
3.3 { 11^7、9^7、7^7 }
3.4 { 5^7 、3^7 }
如果 u32Odd 在 3.1 中，if u32RShift==0 then return TRUE; else return FLASE;
如果 u32Odd 在 3.2 中，if "11|u32RShift" then return TRUE; else return FLASE;
如果 u32Odd 在 3.3 或 3.4 中，if "7|u32RShift" then return TRUE; else return FLASE;
（程序中，并没有直接进行“k|n”的判定，而是通过简单的“==”进行优化）
4、判定是否可表示成 k^r 型，其中 r = 5, 3, 2 之一；
4.1 判定是否可表示成 k^2 型：前提条件：2|u32RShift 且 “8|(u32Odd-1)”(奇数完全平方数被8除必余1)，如果可以表示成 k^2 型，return TRUE;
4.2 判定是否可表示成 k^3 型：前提条件：3|u32RShift，如果可以表示成 k^3 型，return TRUE;
4.3 判定是否可表示成 k^5 型：前提条件：5|u32RShift，如果可以表示成 k^3 型，return TRUE;
5、return FLASE;
优化说明：
一、仅通过是否为素数次幂进行判定，极大地减少了不必要的测试工作；
二、将对整数判定转化为对奇数判定，从而缩小了范围，并为后期预判定提供了快速依据；
三、对大指数型的测试，仅通过比较运算即可排除或肯定，算法非常高效；
四、对完全平方数，先通过是否满足“8|(u32Odd-1)”进行快速筛选；
五、不调用任何系统 math 算法库，不使用任何浮点指令。
最后，to bigc2000(公元2005年4月9日) ：
我说的不是你所说的“我说得16ms问题是1000！”，而是10000!，请注意仔细阅读！Top
43 楼bigc2000（公元2005年4月9日）回复于 2006-08-28 17:25:04 得分 0
你赢了！
10000！我把它看成是阶乘，我不知道windows下calc.exe怎么算的，你说只要16ms，所以我表示怀疑，calc估计也达不到。它超过3万多位。末位联系0的个数都有2499。这个就是我怀疑的地方，所以上面有疑惑，请别见怪
我的算法，相比之下，非常笨重，唯一的好处是对于任意给定的整数具有同一的算法。
下面是运行结果：第一个是你的，第二个是我的，10w个最大数字2^31-1数字
从2147283647 到2147383647 用时15 ms，统计有1个幂数字
2147302921是幂数
从2147283647 到2147383647 用时1450 ms，统计有1个幂数字
2147302921是幂数
如果是debug的话，你的约为170ms，我的约为1800ms。
题外话：本人比较笨，实在看不出来你说的和超超的枚举指数有多大关系。
好了，这个贴我就到此为止了。
你赢了！恭喜Top
44 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2006-08-28 17:45:07 得分 0
要不是为了证明人品问题（“做人要厚道！”），我不会花功夫去研究该算法；至于输赢本无所谓。
而“10000!”也确确实实就是“精确计算并输出10000的阶乘的具体数值”。
我本人对整数类的问题研究得比较多，“HugeCalc”即是多年开发的产物，阁下可从各大下载站点下载体验之。Top
45 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2006-08-28 18:01:24 得分 0
这样的问题，首先生成一个幂数字的文件。
然后每次运行程序的时候都用这个文件来初始化一次。
遇到一个数字就在里面搜索一次就可以了->用内存换时间，
2分搜索你总会吧。Top
46 楼yyfhz（火山）回复于 2006-09-04 13:52:24 得分 0
假设说Y是一个幂数字，则有
Y=(a1*a2*...*an)^(b1*b2*...*bm)，其中a1<=a2<=...<=an, b1<=b2<=...<=bm都是质数。
我们现在来找b1。
b1的最小值当然是2, b1的最大值是Log2(Y)。
记得有一位数学家曾经说过：对于足够大的N, 在数字1~N之间的质数的个数和Log2(N)成正比例。
换言之，当Y很大时，在1~Log2(Y)中，一共有 k*Log2( Log2(Y) )个质数，
这个数量可以说是相当的少了，例如当Y在 10^100 这个范围内，质数的个数大约是200个。
可以整理一个够大的质数表，作为开方的指数。
一般来说，这个质数表能有1000个质数就差不多拉。Top
47 楼mathe（）回复于 2006-09-04 14:27:09 得分 0
yyfhz瞎扯了，在1～N之间的素数个数大约是N/log(N)个（其中log以e为底），这是素数定理Top
48 楼yyfhz（火山）回复于 2006-09-05 13:28:54 得分 0
啊，这个应该是我记错了，谢谢mathe()指出，很久没有碰数学书了，嘿嘿Top
