素数的个数公式 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 E-mail:632158@163.com 摘要：■1.素数的个数公式在素数分布的研究中具有重要的理论意义。 ■2.素数的个数公式的简化计算一直是素数的个数计算中的一个 关键。 关键词：素数、素数的个数公式、筛法函数 中图分类号：0156.1 素数，又称质数，只有两个正因数(1和本身)的自然数。除了1和本身 外还有别的约数的数称之为合数，而1和0既非素数也非合数。在素数中，只有 2为偶数，其余的全为奇数，并且，当素数p>3时，p一定是6k±1的形状(k 为整数)。 对于正整数n,定义π(n)为不大于n的素数总个数。√n表示n的算术平方 根，[V们表示不超过m的最大整数。m为整数，当2≤pp,…pm≤[m们时， PP2…pm表示自然数n的前部质数，m为前部素数的个数，m=π（√n);j 为整数，当Vn<g,q2…q,≤n时，qpq2…q,表示自然数n的后部质数， j为后部素数的个数。所以π(n)=m+j。 定理1：任大于1的整数n,除1外的最小正因数q为素数，并且当n为合 数时g≤√n。证明可以参考《初等数论》郭凤琴编P17 定理2：“若自然数n不能被不大于√n的任何素数整除，则n是一个素 数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。 定理3：（容斥原理)设A,A,…Am是有限集A的子集，4=n,那么A 中所有不属于A,A,…An中任何一个元素个数为： 设4n4n…n4简记为门4.：4U4U…UA简记丸U4 U4-24-24n4a4n4n4-+-l4 那么素数的个数公式 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 E-mail：632158@163.com 摘 要：■1.素数的个数公式在素数分布的研究中具有重要的理论意义。 ■2. 素数的个数公式的简化计算一直是素数的个数计算中的一个 关键。 关键词：素数、素数的个数公式、筛法函数 中图分类号：O156.1 素数，又称质数，只有两个正因数（1 和本身）的自然数。 除了 1 和本身 外还有别的约数的数称之为合数，而 1 和 0 既非素数也非合数。在素数中，只有 2 为偶数，其余的全为奇数，并且，当素数 p＞3 时，p 一定是6 1 k ± 的形状（k 为整数）。 对于正整数 n，定义 π(n)为不大于 n 的素数总个数。 n 表示 n 的算术平方 根，⎡ ⎤ n ⎣ ⎦ 表示不超过 n 的最大整数。m 为整数，当 2≦ 12 m pp p ， ≦ "" ⎡ ⎤ n ⎣ ⎦ 时， 12 m pp p ， 表示自然数 "" n 的前部质数，m 为前部素数的个数，m n = π ( ) ；j 为整数，当⎡ ⎤ n ⎣ ⎦ ﹤q，q q 1 j ２"" ≦n 时，q，q q 1 j ２"" 表示自然数 n 的后部质数， j 为后部素数的个数。所以 π(n)＝m+j。 定理 1：任大于 1 的整数 n，除 1 外的最小正因数 q 为素数，并且当 n 为合 数时q n ≤ 。证明可以参考《初等数论》郭凤琴编 P17. 定理 2：“若自然数 n 不能被不大于 n 的任何素数整除，则 n 是一个素 数”。见（代数学辞典[上海教育出版社]1985 年。屉部贞世朗编。259 页）。 定理 3：（容斥原理）设 1 2 , , AA A "" m 是有限集 A 的子集， A n = ，那么 A 中所有不属于 1 2 , , AA A "" m 中任何一个元素个数为： 设 1 2 1 m m m i AA A A = ∩ ∩""∩ 简记为 ； ∩ 1 2 1 m m m i AA A A = ∪ ∪""∪ 简记为∪ ( ) 1 1 1 1 1 m mm m m m i i i j i jk i i i i j i jk i A A AA AA A A − = = < << = ∪ ∩ = − + − +− ∑∑ ∑ ∩ ∩ ∩ "" 那么