大理建设投资有限公司网站,百度号码查询平台,网站怎么自己优化,尼高品牌设计普通筛法时间界 O(nlnlnn) 的证明 定义 朴素素数筛法即是利用每一个素数筛出所有他的倍数。 证明 对于待筛选的最大数n#xff0c;由于素数分布定理#xff0c;其中的素数个数约等于 nlnn#xff0c;第i个素数约为 ilni。则算法总的运行次数为#xff1a; ∑i1nlnnnilnin∑… 普通筛法时间界 O(nlnlnn) 的证明 定义 朴素素数筛法即是利用每一个素数筛出所有他的倍数。 证明 对于待筛选的最大数n由于素数分布定理其中的素数个数约等于 nlnn第i个素数约为 ilni。则算法总的运行次数为 ∑i1nlnnnilnin∑i1nlnn1ilni…(1) (为了方便计 ln11 ) 考虑对 ∑i1nlnn1ilni…(2) 用积分估值。有 ∑i1nlnn1ilniO(∫nlnn21ilni di)…(3) 由微积分基本定理 (3)O(F(nlnn))…(4)F(x)∫1ilni dilnlni 因而 (2)(4)O(lnlnnlnn)O(lnlnn−lnlnlnn)O(lnlnn) 所以 (1)O(nlnlnn) 证毕。 转载于:https://www.cnblogs.com/ljt12138/p/6684356.html
