--输入任意整数值,输出此数所有因子,或判别是否素数---
原贴:吧里
http://tieba.baidu.com/p/3756650260我的回复:
原理也挺简单的
X由2开始到NUM / 2 , NUM/X 没有余数的就是因子,印出
关键是如何输入,如何转成16进位
想深一层:
....X由2开始到NUM / 2 , NUM/X 没有余数的就是因子.....
这句话没错,但X实际上不用递增到NUM/X。
比如找18的因子,用2去除,没有余数,因此2是因子,但商9也是因子,
而且是最后一个因子,若把9印出来就会乱套,因为还有3,
9没理由排在3之前列印出来,解决方法是PUSH,把9先保存...
接着用3去除,没有余数,3是因子,商6也是因子,再PUSH保存。
我们会看到,除数和商越来越接近,接近到什么位置是中间点呢?
答案是18的平方根,大概是4.24。
除数到了被除数的平方根就不须再递增了,因为平方根之前若有因子,
其[商]都已经被PUSH保存了,只要预先累加PUSH的个数,
再POP回来,根据 [后入先出] 的原理,平方根之后的因子就会如数POP出
18的因子6,9不用计算就被POP出并显示,次序是先6后9。
有了想法,程式读入输入后,先找出平方根,然后用2开去除 [被除数]到平方根为止,
每碰到除尽没有余数就PUSH商,再印出除数,然后除数+1再回去除[被除数],
PUSH之前还比较除数是否等于商,除数=商,相当于 [平方根 x平方根],
若是就不用PUSH了。
这个找因子的程序另一个用途 : 找素数!
若输入的数值没有因子,毫无疑问这是一个素数!
程序包含:
1.找平方根的简易副程序(只传回整数)。(small_sq)
80387有一条平方根指令FSQRT,支援范围是(-7FFFFFFF到7FFFFFFF)
数值是32BIT的一半,因此不采用,自己写了一个简单的,支援无符号的0FFFFFFFFH
2.将输入十进制转十六进制的副程序。(dtoh)
3.输出十进制的副程序。(Printout,输入EAX)
4.速度和复杂度的考量,且涉及32BIT运作,所以部份代码用386暂存器。
本来回圈里的DIV法最耗时,但因为有平方根限制,最大的回圈也不超过64K,就算输入最大值,程序他能瞬间完成,所以就不考虑再优化了。
程式push运作比较多,堆栈须定义大些,否则会无端跳出。
程序支缓最大32bit 即十进制 0-4294967295 (约43亿)的输入。
它可以找到这个范围里,所有数值的因子或者判别是否素数。