素数分解

cfan2021

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

eheotolee

孤立条件的好找

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

ojaupobcisi

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

asukrimukozor

这个个数应该有讲究

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

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

Dennislem

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

anoqejiji

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

erileiyuqig

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

saluozu

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

AbertVab

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

utawomeg

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