素数分解

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;
     
  9. 
     
  10.     for(i=0;i<num/2;i++){
      
  11.         sump+=start.PreviousPrime(start);
      
  12.         sump+=end.NextPrime(end);
      
  13.     }
      
  14. 
      
  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函数的性能不重要,因为被调用次数极少