for(t=p;t<=V;t*=p){///Here t will enumerate all power of p
s=(U/t )*t; if(s<U)s+=t;
for(;s<=V;s+=t){sum-=m;x/=p;}
}
:)
我感觉这个问题的分布计算还是比较好做的
关键是数据频率有点大哦
假设每机器分配100亿每次
则，估计至少产生10^7的数据
（我忘记具体的概率了）
没必要保存这么多数据吧
如果筛选8连续smith Number
则，需要重叠计算
至少重叠16个数字
前8后8
如果将来为了寻找更大的连续
则我想要重叠一个比较大的值
It's trival. Just keep the first 8 and last 8 result of each section in a file. Later we could use a script to analyze them
结果应该不是连续的
会分成一个个的块
使用数据库协调么？
谁今后搞个n-Smith数性测试，一秒钟1万亿多好。:lol
我的想法
筛的算法：筛去素数p,p^2,...,p^n的倍数; (p^n <= end)typedef unsigned char uchar;
uchar sieve; //q*(0 - 999999)
void FACT_BATCH(int beg, int end)
{
int i,j,k,p;
i = 1; p = primetab;
while (p <= (int)sqrt(end))
{
pdigSum = calc_digSum(p); //素数的各个位数的和
//分别筛去 p, p^2, ... ,p^N 的倍数
j = p;
while (j <= end )
{
if (beg % j == 0) then k= beg;
else k = beg +j - beg % j;
//刚才忘记考虑余数为0的情况
while (k <= end)
{
sieve += pdigSum;
k += j;
}
j *= p;
}
i++; p=primetab;
}
//批量素因数分解
}然后比较计数值，也算穷举法。
[ 本帖最后由 suan1024 于 2008-11-30 12:32 编辑 ]
可以这么考虑
分块9699690=2*3*5*7*11*13*17*19
然后循环，剔除小于20素数的因子
只保存两个结果
已经找到的素数的数字和，剩余数字
再进行筛法，剔除余下的素数
则余下数字，就是素数了，计算余下数字的数字和，如果剩余1则不计算
回楼上，这和筛法求素数不一样。对于x,他的所有的素因子p，都必须试除，而且可能要重复多次，直到剩余因子除以p余数不为0为止。
分2步，第一步除掉20以内的因子。第二步除掉其他因子并不到减少除法次数，也不能提高速度。
55楼的算法有比我代码好的地方，分解因数部分比我的更好，可以提高速度，等下次试一试。但这个代码也有一些问题，当beg 的范围很大是，而导致内存的地址很大而无法计算，而我的算法则不会，我的代码稍加改进就可以计算$2^64$以内的smith数。
k = beg + j - beg % j;
while (k <= end)
{
sieve += pdigSum;
k += j;
}
楼上的意思我明白。
55楼的算法有存在严重的漏洞！
还是liangbch的算法正确，少量的试除是必须的！
[ 本帖最后由 suan1024 于 2008-11-30 22:56 编辑 ]
还需要计算$root{3}{n}$,$root{4}{n}$
筛法求素数和分解合数的算法存在较大的差异，少量试除是必不可少的！liangbch的算法正确。