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-=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 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。