算法 讨论一道求质数的面试题

匿名 · 2012年06月04日 · 最后由 hongweiz 回复于 2012年07月22日 · 5528 次阅读

求 2…n 的所有质数

前置知识:

一个数 n 如果不能被 2...n 的数除尽,那么 n 就是一个质数。 但是因为某些原因如果 n 不能被 2…根号 n 的数除尽就足以证明 n 是质数。 又因为某个定理质数只要不被 2...根号 n 之间的质数除尽就可证明其是质数。 如:13 需要证明其不会被 [2,3] 除尽就可知其是质数。 因为我们求的 n 会非常大。所以要用例子中的算法。这意味着要把求出的质数保存下来。

正题:n 非常大 20 的几十次方之类 给你两台计算机,如何做到在两台计算机上计算用的时间约等于使用一台的时间的一半。

注:主要问的是思路 如:如何分割两台计算机分别的计算范围,不涉及具体算法或技术。

匿名 #1 2012年06月04日

顺便说下我用我的手机发不了贴啊,点保存没反应,码了这么多字还是回来复制到电脑上发的。。手机系统是 windows phone。

共享一个已知质数表,然后两台电脑异步算吧。

比如 pc A 算 a, pc B 算 b。如果 a 或 b 是质数,存入共享质数表里,然后 move on。感觉是这么回事。具体实现的话还要有些根据已知质数表过滤肯定不是质数的新数的函数了。

匿名 #3 2012年06月04日

#2 楼 @pepsin 重点就是 a 和 b 怎样取啊,也就是两台电脑按照什么样的范围进行计算 还有要注意时间要求是一台的一半 (大致上)

顺便说下面试挂掉了,所以我也不知道这题答案

可以参考这个帖子 http://ruby-china.org/search?q=%E7%B4%A0%E6%95%B0 我觉得楼主的思路可能和出题者不太一样, 如果用筛选法来考虑这个问题的话,可以轻松设计成 map reduce 的形式计算,n 台计算机所需时间也刚好是 1/n

匿名 #5 2012年06月04日

#4 楼 @paranoyang 这个思路是出题者提示我的。。 另外你说的算法和技术不太了解。不过这个问题是后边的解答要建立在之前的答案上效率才最高。所以如何分割计算范围才是重点,而且我的确是被这样提示的。

对于这道题我也有自己的答案,不过远远达不到一半的时间。先不贴了以免影响别人思路

#5 楼 @jjym 你帖子里说的这种方法比筛选法慢很多很多,建议你还是看一看。

匿名 #7 2012年06月04日

#6 楼 @paranoyang 你在那贴中写的就是筛选法吗? 如果是的话那么这个绝对会比你的效率高。这种筛选是在 2...根号 n 之间且仅限质数,比你的范围少多了

#7 楼 @jjym 呵呵,你再想想。

匿名 #9 2012年06月04日

好吧,我想不出来,等我吃点东西写个这个思路的算法我们比下时间,你说的算法就是那贴中 4 楼那个吧?

#9 楼 @jjym 建议找本算法书看看时间复杂度的概念

#9 楼 @jjym 分布式算质数的话我想了一个办法,不知道能不能满足你的要求

#设置N以内的质数
N = 9999
arr = Array.new(N)
(2..N).each do |num|
    next if arr[num] == 1 
    #***你可以分布式的让多台电脑运行这段代码过滤掉非质数
           num.setp(N,num) do |k|
               Thread.new {   arr[k] = 1}
           end
   #*****
end

然后数组中是 2..N 中是 nil 的都是质数 思路就是因为质数的 x 倍都不是质数,过滤法

匿名 #12 2012年06月04日

#10 楼 @paranoyang

#我的算法
def compute_primes n
  primes ||= [2]
  (3..n).each{|i|
    limit = Math.sqrt(i).to_i
    primes.each{|p|
      break if i % p == 0
      if p >= limit
        primes << i
        break
      end
    }
  }
  primes
end

t = Time.new
result = compute_primes 10000
puts Time.new - t

#paranoyang 的
def prime(m,n)
  a = (2..n).to_a
  a.each do |prime|
    a.reject!{|num| num > prime && num % prime == 0}
  end
  a.delete_if{|p| p < m }
end

t2 = Time.new
result2 = prime 2,10000
puts Time.new - t2

#验证结果
puts result == result2

这个是执行结果

0.019761734
0.213919168
true

这个够明显了吧,本来算得是 1000000,但是所谓筛选法很久都没反映,所以换小了

#12 楼 @jjym 呵呵,你开玩笑的吧。

匿名 #14 2012年06月05日

#11 楼 @tassandar 这个思路貌似可行!!不过 n 太大,计算量太大,估计理论上达不到一半时间! 而且应该是为一个质数开辟一个线程,而不是为一次赋值。。估计手滑了

匿名 #15 2012年06月05日

#13 楼 @paranoyang 请问有什么问题吗?我哪里搞错了?

#14 楼 @jjym 我只是为了体现不同电脑而用了线程,电脑怎么分配任务你应该有一个专门的类。意会思路就行了。

#15 楼 @jjym 速度应该不会慢吧,复杂度可以计算, 应该是 O(N*log2(log2(N)) )

匿名 #18 2012年06月05日

#17 楼 @tassandar 关键你要在 20 的几十次方,这个数量级上去排除。我猜想比直接计算要慢多了。

匿名 #19 2012年06月05日

发下我自己的思路

第一台计算机计算2..根n的质数。

第二台从根n开始计算(根据计算机1的结果,未计算出结果时采用通常算法)
    比如计算机1计算已经计算出了2,3,5,7但还没计算到根n。此时计算机2计算时利用这四个素数,因为7之后还未计算所以从7后采用递增的方法计算(8,9,10,11,12...直到该数的开平方)

等第一台计算完根n后。从n开始向后计算。

这样的话可以起到一定的优化作用,但不知是否能符合答案

如果更进一步优化可以使计算机1计算到根n的二分之一,而计算机2从根n的二分之一开始计算(将上述算法分段后递归)。这样计算机2的结果也可以被利用。

按照我的这种思路第二种应该是极限了,不过感觉应该还有可以更接近一半方法,应该是某种质的飞跃的算法......

睡觉,明天再战

#15 楼 @jjym 呵呵 见笑了,我之前只想了算法,而代码的操作效率都很低,这里同一个算法考虑效率后重写一次。你再看看~


def compute_primes n
  primes = [2]
  (3..n).each{|i|
    limit = Math.sqrt(i).to_i
    primes.each{|p|
      break if i % p == 0
      if p >= limit
        primes << i
        break
      end
    }
  }
  primes
end

t = Time.new
result = compute_primes 1000000
puts Time.new - t

#paranoyang 的
def prime(n)
  primes = Array.new(n, true)
  primes[0] = false
  primes[1] = false
  (2..n).to_a.each do |it|
    if primes[it]
      times = 2
      while it * times <= n
        primes[it*times] = false
        times += 1
      end
    end
  end
  ans = []
  primes.each_with_index{|v,i| ans << i if v}
  ans
end

t2 = Time.new
result2 = prime 1000000
puts Time.new - t2

#验证结果
puts result == result2

最后结果

3.409089914
1.013814049
true

改为 1000 万时的结果:

62.907095532
10.959379423
true

最后是无聊的 100 000 000

1697.931828172
140.165174387
true

这里再说一下多台计算机的思路:

def prime(n)
  primes = Array.new(n, true)
  primes[0] = false
  primes[1] = false
  (2..n).to_a.each do |it|
    if primes[it]
      times = 2
      while it * times <= n
        primes[it*times] = false
        times += 1
      end
    end
  end
  ans = []
  primes.each_with_index{|v,i| ans << i if v}
  ans
end

假设有 x 台计算机。 在 2..n 那个迭代中,把 times 的范围先求出来,也即 2..(n / it - 1)。再将这些数分成 x 个等分的 list,每台计算机对 list 中每个元素做*it运算,并返回该 list,返回的 x 个 list 合并后,将合并结果分发给 x 台计算机,每台计算机维护 primes 素数表的 n/x 位,将 list 中其管辖范围内的 primes 置为 false。这样计算量恰可分为 x 份。

哎呀,我没看清楚题目,原来是要求 2..n 的所有质数。。。

#22 楼 @Juanito 你是来卖萌的啊!

http://ruby-china.org/topics/2582 这帖子里的 qinsine 给的算法http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 似乎可以提高效率很多,你注意那个算法的演示动画,可以设 2 3 5 7 ..sqrt(n) 为基数,然后分配给不同的机器进行那个算法计算,调度器维护一张 2..N 的 hash,另外,根据常识,除 2 以外的所有偶数和除五以外的所有个位为 5 的奇数都不会是素数,所以 2 和 5 两个可以省略掉,这样 3 和 7 交给其他机器计算即可,输出所有素数只需 nums.each_with_index {|n, i| p i unless 两种特殊情况 or n }即可 如果 n 无限大,并且 sqrt(n) 也无限大,可以考虑递归思想计算

举个例子:N=1000 4 台机器 则约定 2 3 5 7 为素数 调度器计算 sqrt(1000) 约等于 32,每台机器计算一个数字 汇总 可以得到 32 以内的素数 然后调度器再平均分配这些素数到 worker,计算然后汇总 就能得到 1000 以内的素数了 这里 worker 可以记录之前的计算结果,从而避免重复计算。 如果 sqrt(n) 依然很大,则不断开方,直到范围有限为止(<120 即可,原因看 wiki 的那个算法演示)

#24 楼 @jasl 我上面写的算法就是这个

匿名 #26 2012年06月05日

#21 楼 @paranoyang 好吧,这种思路和#9 说的有点像。 我没想到消除的效率会这么高,用这种方法的话的确分布计算也很方便。 不过是面试官故意诱导我用的保存质数这种方法。。。这种优化也是他提醒我的。。不知是要考这种算法如何分布计算还是估计误导我。。 另外你们都是在美国吗。。这么晚也不睡

#26 楼 @jjym ...其实我们说的都是一个东西,筛选法...

@jjym @tassandar 筛法和提问者阐述的算法本质一样的(话说这不是很传统的方法吗),不考虑调用栈的时间的话,应该是恰好同样时间的,按照所谓的 “筛法” 的话分布式或许好写一些

匿名 #29 2012年06月08日

#28 楼 @xranthoar 呵呵,我算法不合格啊,对分布式也不了解。 谢谢楼上各位,又学到了不少知识。

#28 楼 @xranthoar 两者的复杂度是不同的,当然你也可以说所有的求质数算法本质都一样。确实是很传统的方法,不过还是很多人弄错不是么

@paranoyang 额。。的确是相同的。。再想想?

@paranoyang 筛法对每一个有相同因子的数给一个标记,那么每个数就会有自己的质因子那么多次操作,而 #1 提出的办法是对每一个数从前面的质数里的整除性来判别是否是质数,有何差别

@paranoyang 所以我说多的是调用栈的时间。

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

#34 楼 @hongweiz

题目是

求 2…n 的所有质数

我觉得很可能答案就是不行...

@bhuztez 大家的算法都差不多哇。。。你也是要存质数表的嘛~估计出题人没考虑这些,提一个大数可能仅仅是为了夸张从而过滤一些低效的方案,而且题目里并没有说明硬件条件。理想状态下,像采用 google 那样的分布式存储集群,存储这些数字本身是有可能的。

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

需要 登录 后方可回复, 如果你还没有账号请 注册新账号