找回密码
 欢迎注册
楼主: medie2005

[讨论] K-Smith numbers

[复制链接]
发表于 2008-11-29 17:05:06 | 显示全部楼层
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[p];x/=p;}
    }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 19:18:27 | 显示全部楼层


我感觉这个问题的分布计算还是比较好做的
关键是数据频率有点大哦

假设每机器分配100亿每次
则,估计至少产生10^7的数据
(我忘记具体的概率了)
没必要保存这么多数据吧
如果筛选8连续smith Number
则,需要重叠计算
至少重叠16个数字
前8后8
如果将来为了寻找更大的连续
则我想要重叠一个比较大的值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 19:22:18 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-29 19:28:22 | 显示全部楼层
结果应该不是连续的
会分成一个个的块
使用数据库协调么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 09:55:25 | 显示全部楼层
谁今后搞个n-Smith数性测试,一秒钟1万亿多好。

我的想法

筛的算法:筛去素数p,p^2,...,p^n的倍数; (p^n <= end)
  1. typedef unsigned char uchar;
  2. uchar sieve[1000000]; //q*(0 - 999999)

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

  25.                 i++; p=primetab[i];
  26.         }
  27. //批量素因数分解  
  28. }
复制代码
然后比较计数值,也算穷举法。

[ 本帖最后由 suan1024 于 2008-11-30 12:32 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 10:18:04 | 显示全部楼层
可以这么考虑
分块9699690=2*3*5*7*11*13*17*19
然后循环,剔除小于20素数的因子
只保存两个结果
已经找到的素数的数字和,剩余数字
再进行筛法,剔除余下的素数
则余下数字,就是素数了,计算余下数字的数字和,如果剩余1则不计算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 10:38:04 | 显示全部楼层
回楼上,这和筛法求素数不一样。对于x,他的所有的素因子p,都必须试除,而且可能要重复多次,直到剩余因子除以p余数不为0为止。
  分2步,第一步除掉20以内的因子。第二步除掉其他因子并不到减少除法次数,也不能提高速度。
  55楼的算法有比我代码好的地方,分解因数部分比我的更好,可以提高速度,等下次试一试。但这个代码也有一些问题,当beg 的范围很大是,而导致内存的地址很大而无法计算,而我的算法则不会,我的代码稍加改进就可以计算$2^64$以内的smith数。
k = beg + j - beg % j;
      while (k <= end)
       {
                   sieve[k] += pdigSum;
                    k += j;
        }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 11:46:48 | 显示全部楼层
楼上的意思我明白。

55楼的算法有存在严重的漏洞!

还是liangbch的算法正确,少量的试除是必须的!

[ 本帖最后由 suan1024 于 2008-11-30 22:56 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 13:29:29 | 显示全部楼层
还需要计算$root{3}{n}$,  $root{4}{n}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-30 23:00:16 | 显示全部楼层
筛法求素数和分解合数的算法存在较大的差异,少量试除是必不可少的!liangbch的算法正确。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 05:18 , Processed in 0.047423 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表