|

楼主 |
发表于 2018-11-12 17:10
|
显示全部楼层
本帖最后由 zengyong 于 2018-11-12 09:29 编辑
3、定理1 是欧拉函数公式,数论教科书都有证明。当2n是2、3、5...、pm的倍数时,可以从容斥公式推出
欧拉公式。换句话说,当2n是2、3、5...、pm的倍数时,容斥公式的所有项都能整除,去除整除号,再化简就能得到欧拉函数公式。
这样,我们就解决了当2n是2、3 、5...、pm的倍数时,如何筛除合数而得到准确的素数个数。例如:当2n=18,18是2、3的倍数,那么
ф(18)=18 (1-1/2)(1-1/3)=6, 有6个与2、3互素的整数,即1,5,7,11,13,17. 那么,当2n=18,有7个素数。 |
|