我最近在招聘方面遇到了这个问题：
给定间隔[L，R]（1
例如L = 3，R = 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的素数，计算出互素数，但是我需要一种比这更好和有效的方法。预先感谢。
l635513504 回答：每个数字的互质数
以下是一种方法。
对于每个数字K，请执行以下步骤：
- 找到K的素因数（让我们将其表示为D）。
- 使用 inclusion-exclusion 原理对[L，R]区间中的数字进行计数，该数字是D中至少一个数字的倍数。该数字表示非数字的计数与K互质。
- 您可以在this answer（属于我的）中看到有关此包含-排除方法的更多详细信息。
- 该问题涉及任意集D（不一定包含素数）-在我们的情况下，D包含素数，因此，该答案的最低公倍数（lcm）调用可以在此处更直接地计算为当前子集中的数字。
- 最后，要找到与K的互素数，请从[L，R]区间的值总数中减去先前找到的数。
备注：在第2步中，我们可以类似地使用包含-排除原理直接计算与K互质的数字（但是，对我来说，更自然地计算K的倍数） D组中的数字）。这将不再需要步骤3。