算法求教:一个数化为几个约数的乘积，且几个约数尽可能相近，不差太大

blavy · 发表于 2016-12-23 13:26:36

一个数化为几个约数的乘积，且几个约数尽可能相近，不差太大，不知道这个算法应该怎么做。
使用均方根来容易出小数，使用类举的方式感觉效率太低，有没有谁做过类似的算法，可供参考一下。

zouzhichao · 发表于 2016-12-23 13:28:54

因数分解

amigenius · 发表于 2016-12-23 13:30:34

看成约炮算法

canspider · 发表于 2016-12-23 14:12:18

算法要看你数据的范围
如果太大，是没法分解的（RSA安全原理）

armok · 发表于 2016-12-23 15:23:47

提示: 作者被禁止或删除内容自动屏蔽

blavy · 发表于 2016-12-28 09:07:56

本帖最后由 blavy 于 2016-12-28 09:15 编辑

armok 发表于 2016-12-23 15:23
“约数算法 ”不是合格的标题。违反版规11。请立即阅读版规(点击进入: http://www.amobbs.com/thread-56 ...

莫大，由于这几天都没时间上线，现在才看到，违反了规定，很不好意思。以后会注意。
只是现在已经失去编辑权限，只能在回复里说明一下了，或者能否麻烦工作人员恢复一下权限我操作一下。

haihuawu · 发表于 2016-12-28 14:48:05

这还真没有，只能一个一个除。要不然哥德巴赫猜想早被人算出来了。

NJ8888 · 发表于 2016-12-28 14:52:34

haihuawu 发表于 2016-12-28 14:48
这还真没有，只能一个一个除。要不然哥德巴赫猜想早被人算出来了。

除是有选择的，最简单是所有偶数都带2，穷举就少一半

，然后所有位数加==3那就是3约数。。。。。。。。。

NJ8888 · 发表于 2016-12-28 14:54:52

blavy 发表于 2016-12-28 09:07
莫大，由于这几天都没时间上线，现在才看到，违反了规定，很不好意思。以后会注意。
只是现在已经失去编 ...

说明你发帖并不特别关注啊

blavy · 发表于 2016-12-28 15:09:39

本帖最后由 blavy 于 2016-12-28 15:12 编辑

NJ8888 发表于 2016-12-28 14:54
说明你发帖并不特别关注啊

主要是这年底了，这会那会，这赶那赶的，时间一下子就没有了。

这个算法我现在只能是从1开始一个一个除下去，除到255，把除得尽的存下来，后面再查表以求达到目的了。
刚开始是想把一个数分解成质数的积1、2、3、5、7.。。。。，后面发现这对大的数来说后面的组合比较麻烦，因为要把这个源数弄成几个相近的数相乘，分得太散很容易取错

nengcai0313 · 发表于 2016-12-28 16:00:21

如果是255以下的，不如先算好，做张表。255以上的，先判断最后一位的条件，分奇偶，少一半运算，而且不需要完全遍历，算到方根就可以了。

Xiyuhexuan · 发表于 2016-12-28 16:44:39

amigenius 发表于 2016-12-23 13:30
看成约炮算法

哈哈犀利的眼神！

blavy · 发表于 2016-12-29 14:02:42

Xiyuhexuan 发表于 2016-12-28 16:44
哈哈犀利的眼神！

那是相当犀利

Xiyuhexuan · 发表于 2016-12-29 14:30:18

blavy 发表于 2016-12-29 14:02
那是相当犀利

哈哈

armok · 发表于 2016-12-29 15:12:36

提示: 作者被禁止或删除内容自动屏蔽

redroof · 发表于 2016-12-29 15:38:02

canspider 发表于 2016-12-23 14:12
算法要看你数据的范围
如果太大，是没法分解的（RSA安全原理）

对。这才是懂得的人。
楼主就是想要分解质因数啊！
要是成功了，RSA就完蛋了，HTTPS等等这些东西也一起都完蛋了

brother_yan · 发表于 2016-12-29 16:54:25

要看多大的数，以及平台

blavy · 发表于 2016-12-30 16:29:29

armok 发表于 2016-12-29 15:12
放你一马。

莫大，多谢，多谢

canspider · 发表于 2016-12-30 16:34:47

楼主直接说你的应用场景吧

xivisi · 发表于 2016-12-31 11:15:01

楼主说是分解为几个值相近的约数……
稍微好一点的办法，就是求几个约数就算几次方根，取整后，上下浮动范围内找合适的值，最差情况就是质数了，一个质数n，的5个最相近的约数1*1*1*1*n

myxiaonia · 发表于 2016-12-31 13:12:02

但是到底是几个却没说明，如何决定是分解成2个，还是多个

redroof · 发表于 2016-12-31 13:46:22

myxiaonia 发表于 2016-12-31 13:12
但是到底是几个却没说明，如何决定是分解成2个，还是多个

是几个没人知道

如果数字大一点，整个地球上都别想有人知道。
不要忘了这就是RSA所依赖的分解质因数难题啊

redroof · 发表于 2016-12-31 14:04:34

blavy 发表于 2016-12-28 15:09
主要是这年底了，这会那会，这赶那赶的，时间一下子就没有了。
这个算法我现在只能是从1开始一 ...

你试一下这个数吧，告诉我结果
看你用什么方法算的比较快

12345678909876543210123456789098765432101

blavy · 发表于 2017-1-4 09:15:07

redroof 发表于 2016-12-31 14:04
你试一下这个数吧，告诉我结果
看你用什么方法算的比较快
123456789098765432101234567890987 ...

我来补充一下，数字在无符号32位长度容量，分解成几个100以内的数的积。

redroof · 发表于 2017-1-4 09:26:10

blavy 发表于 2017-1-4 09:15
我来补充一下，数字在无符号32位长度容量，分解成几个100以内的数的积。 ...

只管100以内的数那就简单了，直接试除就行了。一个一个试。
优化一点可以对偶数只试除偶数，奇数只试除奇数。也就是只要试50次以内

阿莫论坛20周年了！感谢大家的支持与爱护！！