素数分解

mathe

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个连续素数之和如何？

无心人

孤立条件的好找

组合的么?
莫非你有想法？

mathe

只是觉得光前面那些条件得出的结果太小了，需要增强增强

无心人

这个个数应该有讲究

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

media2005的程序C++用的太精炼
看不懂

mathe

他的程序假设已经有个素数表计算好了，保存在一个文件里面。（没有注释，比较难看懂呀）
然后就一次计算连续若干个素数和并且判断是否素数，并且保存在一个map里面。

mathe

其中判断一个数是否素数使用Miller_Rabin_Test，应该是相对比较慢的部分，所以应该尽可能少的调用。
这部分有很多优化机会。其实只有一个数字可以表示成各种素数和的情况下我们才需要判断是否素数，而不是先判断是否素数再判断是否表示成各种和的形式

无心人

此题目算法的不同步骤组合很关键阿

medie2005

呵呵，我那个代码只是为了解google treasure hunt 2008 中的primes而写的，效率是不高。
这个问题，也没有什么数学知识可利用，只能硬搜，当然还需要技巧。
除了mathe所说的优化外，由于map很占内存，其实可以在计算过程中，从map中去除一些已经不可能的节点，以节省空间。
Miller_Rabin_Test()函数和PowModular()函数也都还可以优化。

无心人

如果是32位内的可以利用汇编优化算法
对于素性检测有4倍以上的速度提升

无心人

毕竟汇编可直接检测bit位
且模乘算法是两条指令就得到结果的