• 讨论一道求质数的面试题 at 2012年07月22日

    @bhuztez 不要说可能。没有分析,没有证明,没有说服力。

  • 讨论一道求质数的面试题 at 2012年07月20日

    @jasl @paranoyang N 的量级是 20 的几十次方,比如 20 的 20 次方是 104857600000000000000000000,使用筛选法,相当于要把这些个数字都存下来,不太现实。用磁盘存都要 104857600000000 T 的空间,这基本上是不可实现的。 我给出一个算法,大家看看是否可行:

    1. 假定现有的质数表为 a1, a2, a3, ai
    2. 则产生一个子任务,计算 ai 到 ai^2 的质数;
    3. 第 2 步中产生大于 ai 的下一个质数 ai+1 后,可以产生一个新的子任务 ai^2a(i+1)^2,可以分配给另外一台机器; 举例子: 现在已经产生了 2,3,7, 其中一个子任务是计算 8-49 的质数,计算时,很快发现 11 也是质数,更新质数表,又产生一个新的子任务 49-121,完全可以在另一个计算机计算,后来有发现 13 也是,可以产生 121-169 的子任务,也提交到另外一个计算机,随着这个过程继续,不断产生更多的子任务,但是这些子任务都是可以独立运行的,不过要按顺序来,这样可以认为整个过程是两台或多台机器并行执行,是一台机器的 1/2。