2013年6月24日星期一

Prime Checker With Cache

如果需要频繁检查某个数是否是素数,可以把查过的素数缓存下来。
 
 

class PrimeCheckerWithCache:
 def __init__(self):
  self.primeSet=set([2,3])
  self.maxTested=4
 def isPrim(self, test):
  #cache hit
  if test<=self.maxTested:
   return test in self.primeSet
  #test and update cache
  for i in range(self.maxTested+1,test+1):
   if not any([i%p==0 for p in self.primeSet]):
    self.primeSet.add(i)
  self.maxTested=test
  return test in self.primeSet 
 
 
正确性证明:
不变量:primeSet中是不超过maxTested的全部素数。
初始:手动设置,成立。
保持:注意到,每次加入primeSet的,总是不能被任何已知素数整除的最小的自然数,也就是primeSet之外最小的素数。因此不变量保持。

因为素数密度很小,所以都缓存下来在规模较小时是可行的。

关于素数密度(不超过n的素数个数/n),我最近学习到有一些有意思的事实
1、素数无穷多
2、素数的密度收敛到0
3、素数的密度比平方数大:)呵呵没想到吧

没有评论: