3、公式在证明素数定理之前先给出几个定理：定义：设n为正整数，所有小于n而与n互素的正整数的个数，由n唯一决定，是定义在正整数集上的一个函数，称为欧拉两数，记作0(/7)。当n>l时,由定义易知,(p(n)<(n-1),并且(p(h)=n-l充要条件是n为素数。为了理论上的完整，我们规定0(1)=1。下面我们不加证明给出欧拉函数的两个定理，证明可以参考初等数论。定理1：若(npn2)=l,那么(p(n心=。定理2：设n为正整数,p加为n的前部素数,那么（p（n）=7r（n）-m+l□证明：设n为正整数，Pm为n的前部素数，若心……kp_^kr={pq^rq为整数}是卩的
4、剩余类。不难知道，所冇整数均匀分布在这p个剩余类屮，若在1,2,,n内任取一个整数a则pIa的概率定义为1/p,那么p不整除a的概率即为1--,若p<4^是素数，每一个p能否有p不整除a可视为独立事P件，故在1，2,,n内，任取一数b不能被p整除的概率为Y［（l-丄），在1,2,,pgjnPn内，不能被p整除的就是后部素数和1,因为前部索数是能被p整除的，pp.所以A?匸［（1-丄）等于后部质数的个数加1,乂因为前部素数的个数为m,处2）»口（1-丄）p<}nPpgjnP因此,龙（〃）=加+〃匚［（1一~）-1,所以我们有兀（/?）=加+0（〃）一1。p<4nP即
5、:（p（n）=n（n）-zn+1,命题得证。定理3:设n为正整数，不超过正整数n的素数的个数为龙（斤）=加+/1匸［（1-丄）-1。p
6、,“2,几为n的前部素数，若%,匕,……kp_^kr={Piq+rq为整数}是门的剩余类。不难知道，所冇整数均匀分布在这卩个剩余类中，若在1，2,,n内任取一个整数a则PiIa的概率定义为丄，那么Pi门不整除a的概率即为1-丄，若p.<^是素数，每一个p.能否有p.不整除a可视为独Pi立事件，故在I,2,,n内，任収一数b不能被p、，P2,……必”整除的概率为匸［（1一一）0在1,2,,n内，不能被P
7、，P2,……几整除的就是后部素数和1,/=1Pim1因为前部索数门是能被门整除的，即PiPio所以«n（i-一）等于后部质数的个数加1,/=!Pi又因为前部素数的个数为m,所以我们有，不超过正整数n的素数的个数为加]/r(n)=m+叮1(1——)一1。/=!Pi加1推论1：设n为正整数，Pig,几为n的前部索数，那么0(几)=〃匸［(1)of=lPi也可以简记为(p(n)=nF［(i-£)。pS、历P定理4：(Euler乘积公式)设f(n)满足/(^^2)=,且2/0)
8、<8，贝U：/
9、=1£/仪)=口［1+/(")+/(卩2)+/(”)……
10、n=p证明：由于J
11、
12、/(n)
13、
