素数分解

mathe

找到问题所在了,是函数is_list开始多了一行 if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF; 整个程序运行挺快,应该不到一分钟,不过没有找到任何结果.

mathe

看来需要一个分段筛素数的代码

无心人

我记得本论坛有 你仔细找下 不过不要太复杂的

mathe

我的想法是实际上上面代码中只有俩部分计算需要素数列表,也就是计算sumMF和sumMS部分.与其开始保存了所有素数的列表,不如俩部分都动态生成,比如保存两个长度为1,000,000左右大小范围内的素数,分别在当前iMF和iMS指向的数据附近(这两个指针移出范围时计算一下段数据).这样,每一段素数我们需要筛选两次,但是可以避免使用大量内存的问题.

gxqcn

不知问题出在哪里了？ 我这里估计无法调试，因为内存太小了。 粗看了遍代码，有以下几点供参考：

• is_list(..)函数可以精简为
  1. bool is_list(int num, unsigned long long sum)
  2. {
  3. unsigned long long aver=sum/num;
  4. if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;
  5. integer sump(aver);
  6. sump.NextPrime(sump);
  7. integer start(sump),end(sump);
  8. int i;
  10. for(i=0;i<num/2;i++){
  11. sump+=start.PreviousPrime(start);
  12. sump+=end.NextPrime(end);
  13. }
  15. if(sump<integer(sum)){
  16. while(sump<integer(sum)){
  17. sump-=start;
  18. sump+=end.NextPrime(end);
  19. start.NextPrime(start);
  20. }
  21. }else{
  22. while(sump>integer(sum)){
  23. sump-=end;
  24. sump+=start.PreviousPrime(start);
  25. end.PreviousPrime(end);
  26. }
  27. }
  28. return sump==integer(sum);
  29. }

  复制代码
  在帮助文档中对此用法有特别交代说明，其实该用法你在“int prevc,nextc;”语句前已用了一次。
• “if(aver>=0xFFFFFFFFLL)aver=0xFFFFFFFF;”——这句用意何在？ 如果是想限定素数仅用32bits以内的，其后的代码直接用plist里的数据效率更佳

无心人

这个问题怎么说呢 感觉找到答案主要在于运气

gxqcn

编辑了半天帖子，等提交后才知道你们已经知道问题所在了。 不过，我也对那句感到不解和疑惑。

mathe

原帖由 gxqcn 于 2008-6-26 08:43 发表 不知问题出在哪里了？ 我这里估计无法调试，因为内存太小了。 粗看了遍代码，有以下几点供参考：

is_list(..)函数可以精简为bool is_list(int num, unsigned long long sum) { unsigned long long ave ...

我已经找到问题了,就在你列出的第2点这句代码上.原先代码之用于搜索32比特以内范围的数,所以有了这句,后来修改以后忘了删除这句了

mathe

原帖由 无心人 于 2008-6-26 08:44 发表 这个问题怎么说呢 感觉找到答案主要在于运气

从计算速度来看,问题不是很大,结合分段筛划上较长时间应该能够解决这个问题的

mathe

原帖由 gxqcn 于 2008-6-26 08:43 发表 不知问题出在哪里了？ 我这里估计无法调试，因为内存太小了。 粗看了遍代码，有以下几点供参考：

is_list(..)函数可以精简为bool is_list(int num, unsigned long long sum) { unsigned long long ave ...

说明一下: i)开始我采用start.NextPrime(start);这种用法,不过有点不放心这种用法是否可以(毕竟输入输出在同一个地址),帮助文件里面没有说明.此外,帮助中应该还要说明函数NextPrime()会修改*this,然后返回*this; ii)is_list函数的性能不重要,因为被调用次数极少