每个数字的互质数
Count of Coprimes for each number
我最近在招聘挑战中遇到了这个问题：
给定一个区间[L,R]（1 <= L,R <= 10^5），我们需要为[L, R].
例如大号 = 3, 右号 = 7
对于 K = 3，[3, 7] 中的互质数 = 3 (4, 5, 7)
对于 K = 4，[3, 7] 中的互质数 = 3 (3, 5, 7)
对于 K = 5，[3, 7] 中的互质数 = 4 (3, 4, 6, 7)
...
通过我的方法，我找到了最大为 R 的素数，然后对于每个 K，通过它的素因数，计算互素数，但我需要比这更好和更有效的方法。提前致谢。
一种方法如下。
对每个数字 K 执行以下步骤：
- 求出K的质因数（记为D）
- 利用包含-排除原则统计[L,R]区间内的数是D中至少一个数的倍数。这个数将代表与 K 不互质的数字。
- 您可以在
（我的）中看到有关这种包含-排除方法的更多详细信息。
- 该问题涉及任意集合 D（不一定由素数组成）——在我们的例子中 D 包含素数，因此从该答案调用的最小公倍数 (lcm) 可以在此处更直接地计算为乘积当前子集中的数字。
- 最后，要找到与 K 互质的数量，请从 [L, R] 区间中的值总数中减去先前找到的数量。
备注：在第2步中我们可以类似的使用包含排除原理直接统计与K互质的数（不过我感觉更自然计算 D 组中数字的倍数）。这将不再需要第 3 步。
我最近在招聘挑战中遇到了这个问题：
给定一个区间[L,R]（1 <= L,R <= 10^5），我们需要为[L, R].
例如大号 = 3, 右号 = 7
对于 K = 3，[3, 7] 中的互质数 = 3 (4, 5, 7)
对于 K = 4，[3, 7] 中的互质数 = 3 (3, 5, 7)
对于 K = 5，[3, 7] 中的互质数 = 4 (3, 4, 6, 7)
...
通过我的方法，我找到了最大为 R 的素数，然后对于每个 K，通过它的素因数，计算互素数，但我需要比这更好和更有效的方法。提前致谢。
一种方法如下。
对每个数字 K 执行以下步骤：
- 求出K的质因数（记为D）
- 利用包含-排除原则统计[L,R]区间内的数是D中至少一个数的倍数。这个数将代表与 K 不互质的数字。
- 您可以在
- 该问题涉及任意集合 D（不一定由素数组成）——在我们的例子中 D 包含素数，因此从该答案调用的最小公倍数 (lcm) 可以在此处更直接地计算为乘积当前子集中的数字。
- 您可以在
- 最后，要找到与 K 互质的数量，请从 [L, R] 区间中的值总数中减去先前找到的数量。
备注：在第2步中我们可以类似的使用包含排除原理直接统计与K互质的数（不过我感觉更自然计算 D 组中数字的倍数）。这将不再需要第 3 步。