Mobius函数在古典筛法上的应用

The Application of Mobius Function to Classical Sieving Method

找出一个大整数范围内的所有素数是数论中被研究最广泛的一个课题,其中素数的数量、素数的分布、素数表的构造都依赖于现存找到的素数,古典筛法是寻找素数的一个有效的方法.通过Mobius函数及其独特性质从理论上证明古典筛法的有效性,为寻找素数提供一个简洁而实用的算法,并给出筛法原理中一个漂亮的上界估计.

Finding all primes within a large range of integers is one of the most widely studied problems in number theory.The number of primes,the distribution of primes and the construction of prime table all depend on the existing primes.The classical screening method is an effective method to find prime numbers.In this paper,the effectiveness of classical sieving method is proved theoretically through the Mobius function and Its'unique properties,which provides a simple and practical algorithm for finding prime numbers.A nice upper bound estimate of the sieving principle is given.