algorithm - 如何有效地找到整数区间的素数

Question

我有一个整数区间 [a, b] 并将每个单独的整数最初视为一个 1 元素集。然后我想合并所有共享一个共同主要因素的集合。

该任务的解决方案大纲指出，我只需要考虑小于区间大小的素数因子，因为至多一个整数可以将该素数作为因子。

我只是想知道仅考虑主要因素是否还不够<= interval.size() / 2？上述陈述不是自动适用于所有素数> interval.size() / 2吗？

标签： algorithmprimes