K-Smith numbers

mathe

for(t=p;t<=V;t*=p){///Here t will enumerate all power of p s=(U/t )*t; if(s-=m[p];x/=p;} }

无心人

我感觉这个问题的分布计算还是比较好做的 关键是数据频率有点大哦 假设每机器分配100亿每次 则，估计至少产生10^7的数据 （我忘记具体的概率了） 没必要保存这么多数据吧 如果筛选8连续smith Number 则，需要重叠计算 至少重叠16个数字 前8后8 如果将来为了寻找更大的连续 则我想要重叠一个比较大的值

mathe

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

无心人

结果应该不是连续的 会分成一个个的块 使用数据库协调么？

suan1024

谁今后搞个n-Smith数性测试，一秒钟1万亿多好。 我的想法 筛的算法：筛去素数p,p^2,...,p^n的倍数; (p^n <= end)

1. typedef unsigned char uchar;
2. uchar sieve[1000000]; //q*(0 - 999999)
4. void FACT_BATCH(int beg, int end)
5. {
6. int i,j,k,p;
7. i = 1; p = primetab[i];
8. while (p <= (int)sqrt(end))
9. {
10. pdigSum = calc_digSum(p); //素数的各个位数的和
12. //分别筛去 p, p^2, ... ,p^N 的倍数
13. j = p;
14. while (j <= end )
15. {
16. if (beg % j == 0) then k= beg;
17. else k = beg +j - beg % j;
18. //刚才忘记考虑余数为0的情况
19. while (k <= end)
20. {
21. sieve[k] += pdigSum;
22. k += j;
23. }
24. j *= p;
25. }
27. i++; p=primetab[i];
28. }
29. //批量素因数分解
30. }

复制代码

然后比较计数值，也算穷举法。 [ 本帖最后由 suan1024 于 2008-11-30 12:32 编辑 ]

无心人

可以这么考虑 分块9699690=2*3*5*7*11*13*17*19 然后循环，剔除小于20素数的因子 只保存两个结果 已经找到的素数的数字和，剩余数字 再进行筛法，剔除余下的素数 则余下数字，就是素数了，计算余下数字的数字和，如果剩余1则不计算

liangbch

回楼上，这和筛法求素数不一样。对于x,他的所有的素因子p，都必须试除，而且可能要重复多次，直到剩余因子除以p余数不为0为止。 分2步，第一步除掉20以内的因子。第二步除掉其他因子并不到减少除法次数，也不能提高速度。 55楼的算法有比我代码好的地方，分解因数部分比我的更好，可以提高速度，等下次试一试。但这个代码也有一些问题，当beg 的范围很大是，而导致内存的地址很大而无法计算，而我的算法则不会，我的代码稍加改进就可以计算$2^64$以内的smith数。

k = beg + j - beg % j; while (k <= end) { sieve[k] += pdigSum; k += j; }

suan1024

楼上的意思我明白。 55楼的算法有存在严重的漏洞！ 还是liangbch的算法正确，少量的试除是必须的！ [ 本帖最后由 suan1024 于 2008-11-30 22:56 编辑 ]

无心人

还需要计算$root{3}{n}$, $root{4}{n}$

suan1024

筛法求素数和分解合数的算法存在较大的差异，少量试除是必不可少的！liangbch的算法正确。