我想计算 [1,x] 范围内 n 的互质数。我尝试过使用 euler phi 函数，但它给出了 [1,n]。任何人都可以建议修改 euler phi 或任何其他方法来执行此操作吗？ 我使用了 phi(n) = n* (1-(1/p)) 的乘积，其中 p 是 n 的质因数。
最佳答案
您可以使用Inclusion-Exclusion Principle
找到 N 的唯一质因数(它们不能超过 10-12，考虑到 N 和 X <=10^10)。
现在你只需除以即可找到<=x且能被'y'整除的数字的个数。尝试 y 的 n 因子的所有组合(在最坏的情况下您只会得到 2^10 (1024))。 现在使用包含排除来查找 n 小于 x 的互质数。
The idea is that if a number is not co-prime to n, then it will have at least one prime factor common with n.
对于我们这里的示例，让我们考虑 X=35 和 N=30
首先找到该数的唯一质因数。 (其数量不得大于10-12)。 N 的唯一质因子 ={2,3,5}。
求每个因子PAIR的乘积。 {2x3、2x5、3x5 或 6、10、15}。
求每个因子 TRIPLET 的乘积:{ 2x3x5 或 30}。
重复此操作，直到所有因子相乘:{N=30，无需更多步骤}。
计算 X 除以步骤 1 中每个因子的总和:{X=35: (35/2)+(35/3)+(35/5) = (17+11+7)= 35}
求 X 除以第 2 步中每个数字的总和:{X=35: 35/65+3+2=10}
求 X 除以第 3 步中每个数字的总和:{X=35: 1}
重复步骤 4 直至吸收所有结果:{x=35 无需执行更多步骤}
[1..X] = X - step5 + step6 - step7 等范围内 N 的互质数。{N=30，X=35 由 35 - 35 + 10 - 1 给出= 9}。
For N=30, X=60 you will have:
60 - (60/2 + 60/3 + 60/5) + (60/6 + 60/10+ 60/15) - (60/30) = 60 - (30+20+12) + (10+6+4) - 2 = 60 -62 + 20 - 2 = 16.
假设 X = 10。N = 6 = 2 * 3。
我们有数字 {1, 2, 3, ..., 10}。
删除 2 的所有倍数。您将得到:{1, 3, 5, 7, 9}。
删除 3 的所有倍数。您将得到:{1, 5, 7}。
我们如何有效地计算这个？尝试回答这个问题:[1, X] 中有多少个数可以被 p 整除？是地板(X/p)，对吗？即 p, 2p, ..., kp，其中 kp <= X。因此，我们可以从 X 中减去 Floor(X/p)， 即可得到 [1, X] 中与 p 互质的数的个数。
在此示例中，有 10 个数字。能被 2 整除的数字个数是 10/2，即 5。因此，10-5 = 5 个数字与 2 互质。同样，有 10/3=3 个数字是 3 的倍数。所以，我们可以说有 5-3=2 个数与 2 和 3 互质？不，因为你重复计算了!为什么？ 6 已包含在 p = 2 和 3 的计数中。因此我们必须通过添加 2 和 3 的倍数来解决这一问题。[1, 10] 中只有一个 2 和 3 的倍数，即 6。所以，加1。也就是说，答案是10 - 5 - 3 + 1 = 3，这是正确的。
这一点的概括就是包含和排除原则。对于每个 n，我们只是找到它的质因数，我确信它会小于 10 左右。这是使用埃拉托斯特尼筛法，然后进行质因数分解来完成的。 (由于 X < 10^9，一个数的质因数最大数量会更少。尝试找出前 10 个质数的乘积。它将是:6469693230，大约为 64*10^9。(i考虑最大限制为 10^10。这可以很容易地扩展到像 10^18 这样的大数字。)
我希望这有帮助!!
关于c++ - 如何计算 [1,x] 范围内 n 的互质数，其中 x 可以与 n 不同？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17120749/