数学研发论坛

 找回密码
 欢迎注册
查看: 11469|回复: 83

[擂台] 素数分解

[复制链接]
发表于 2008-6-18 18:23:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
http://topic.csdn.net/u/20080606 ... 5-10793bbf18fd.html

找出满足以下条件的最小素数:
a.3个连续素数的和
b.17个连续素数的和
c.45个连续素数的和
d.979个连续素数的和
e.本身为素数

例如:41为满足以下条件的最小素数:
a.3个连续素数的和(11 + 13 + 17 = 41)
b.6个连续素数的和(2 + 3 + 5 + 7 + 11 + 13 = 41)

不过我觉得难度有点偏小,我们再加一个条件
f. 2007个连续素数之和如何?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-18 18:27:14 | 显示全部楼层
孤立条件的好找

组合的么?
莫非你有想法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-18 18:39:46 | 显示全部楼层
只是觉得光前面那些条件得出的结果太小了,需要增强增强
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-18 18:45:15 | 显示全部楼层
这个个数应该有讲究

应该是迭代增强的
找到符合小数字的
再应用到长序列

media2005的程序C++用的太精炼
看不懂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-18 18:53:13 | 显示全部楼层
他的程序假设已经有个素数表计算好了,保存在一个文件里面。(没有注释,比较难看懂呀)
然后就一次计算连续若干个素数和并且判断是否素数,并且保存在一个map里面。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-18 18:56:43 | 显示全部楼层
其中判断一个数是否素数使用Miller_Rabin_Test,应该是相对比较慢的部分,所以应该尽可能少的调用。
这部分有很多优化机会。其实只有一个数字可以表示成各种素数和的情况下我们才需要判断是否素数,而不是先判断是否素数再判断是否表示成各种和的形式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-18 19:39:09 | 显示全部楼层
此题目算法的不同步骤组合很关键阿
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-19 14:47:41 | 显示全部楼层
呵呵,我那个代码只是为了解google treasure hunt 2008 中的primes而写的,效率是不高。
这个问题,也没有什么数学知识可利用,只能硬搜,当然还需要技巧。
除了mathe所说的优化外,由于map很占内存,其实可以在计算过程中,从map中去除一些已经不可能的节点,以节省空间。
Miller_Rabin_Test()函数和PowModular()函数也都还可以优化。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-19 15:07:28 | 显示全部楼层


如果是32位内的可以利用汇编优化算法
对于素性检测有4倍以上的速度提升
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-19 15:13:00 | 显示全部楼层


毕竟汇编可直接检测bit位
且模乘算法是两条指令就得到结果的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-1-22 06:16 , Processed in 0.050526 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表