aimisiyou 发表于 2015-9-11 16:08:30

求个数

1<=K<=N，求不大于N的自然数中与K互质的数的个数？

cn8888 发表于 2015-9-11 16:22:15

先将k分解质因数.不同的素数因子分别是p1,p2....pt
在1到N中，利用筛法，筛掉p1的倍数
再筛掉p2的倍数
..............
再筛掉pt的倍数。
然后得到剩下的个数就可以了

aimisiyou 发表于 2015-9-11 16:34:29

能否用欧拉函数表示呢？在区间中随机取两数，其互质的概率是多少？

倪举鹏 发表于 2015-9-11 19:13:11

aimisiyou 发表于 2015-9-11 16:34
能否用欧拉函数表示呢？在区间中随机取两数，其互质的概率是多少？

没记错的话，一万个数学之谜这本书上说两个数互质概率PI/6

cn8888 发表于 2015-9-12 08:02:02

cn8888 发表于 2015-9-11 16:22
先将k分解质因数.不同的素数因子分别是p1,p2....pt
在1到N中，利用筛法，筛掉p1的倍数
再筛掉p2的倍数


我猜想这个问题的解答如下：
先将k分解质因数.不同的素数因子分别是p1,p2....pt
然后N*（1-1/p1）*(1-1/p2)*(1-1/p3)...*(1-1/pt)，取上整，比如3.4取上整是4

我只是猜想，但是没有任何证明，只是直觉！

aimisiyou 发表于 2015-9-12 08:58:03

cn8888 发表于 2015-9-12 08:02
我猜想这个问题的解答如下：
先将k分解质因数.不同的素数因子分别是p1,p2....pt
然后N*（1-1/p1）*(1-1 ...

好像你的结论是对的!

liangbch 发表于 2015-9-14 18:13:38

对于正整数n>=1,所有的互质(最简）分数a/b (0 <= a <= b <=n)的个数的极限是0.3039635509*(n^2),参见http://mathworld.wolfram.com/FareySequence.html
页: [1]
查看完整版本: 求个数