求个数

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

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

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

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

没记错的话，一万个数学之谜这本书上说两个数互质概率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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 求个数