K-Smith numbers

无心人

我想那个时间,是他无法承受的了
能连续30天计算一个问题的
只有我和mathe能

无心人

如果优化到1秒内能扫描一个亿
我不介意再挂30天

liangbch

这个太夸张了。这个程序已经很优化了，再将其速度提高30倍，几乎是不可能的。

   还有，也可以不用连续运行30天。在运行过程中，定期将运行的中间数据（上下文）保存到文件。这个程序在运行时，如果没有发现程序上下文文件，则从开头运行。否则，将最近的上下文数据从文件载入，从上次运行点接着运行。这个做法，我在那个查孪生小素因子数种已经试用过了，效果很好(可随时中断）.

无心人

有的算法是无法保存状态的

liangbch

怎么不可以，好像没有这样的例子吗？笔记本电脑的运行状态都可以整个保存到硬盘上。

以计算smith数为例，需要记录的数据有以下几个部分

  1. 素数表，当然如果素数比较多，则可以不保存，在下次计算时重新生成。
  2. 10000以内的数的数字和。
  3.上次筛出的最近的10个smith数。
  4.上次筛的范围。如上次从begin 筛到end,那么这次则从end+1 开始筛。

无心人

你没考虑非正常中断的情况

另外，比如树等高级结构很难保存
除非用标准库

mathe

I have a suggestion. We're looking for K-Smith numbers no more than $10^12$ and Yao has a plenty of machines and it is better we could find an efficient distributed algortihm.
For each machine, in the initialization phase, it could find all primes no more than $10^6$
And the compute should also compute sum of digits of all primes less than $10^6$ in advance.
initialized a mapping m[..] so that m[p] to be sum of digits of p.
Now a machine will try to find all K-smith numbers in the range [U,V].
For each number in the range, calculate the sum of digits of the number and save it in an integer array sum[U..V], and create another array x[U..V] which is initialized to the number itself.
Next, for each prime p in the list.
    for(t=p;t<=V;t*=p){
          s=(U/t )*t; if(s<U)s+=t;
         for(;s<=V;s+=t){sum-=m[p];x/=p;}
    }

After that, we could scan the array sum and x by
  for(t=U;t<=V;t++){
     if(sum[t]<0)continue;
    if(sum[t]==0){
          if(x==1) output(t);
    }else{
         if(x>1){
              if(sum of digits of x is sum[t]) output(t);
        }
   }
}

mathe

Since multiplication is faster the divid, we could initialize array x to be 1 and in the first loop, replace x/=p by x*=p
In the second loop, the if(x==1) is changed to if(x==s) and
  if(x>1)  if(sum of digits of x is sum[t])
   changed to
  if(x<s) if(sum of digits of s/x is sum[t])

mathe

It seems liangbch has used the algorithm. So the only suggestion is use * instead of /.

liangbch

mathe 的算法描述有漏洞，
  1.   

for(;s<=V;s+=t){sum-=m[p];x/=p;}

    如果x能够被p整除，要一直除下去，直到不能整除为止。 如60/2=30, 继续除以2， 30/2=15。