乍一看这题，我们立马会有这样的思路： 代码描述，应该很易懂 _ 也就简简单单20行代码，但是这样会带来什么问题呢？ 注意到左界限和右界限的可能差值为200000， 算法的时间复杂度为O(n²)，这样肯定爆TLE！那么怎么来解决呢？ 看这幅图： 看出什么问题来了吗？ 是的，我们其实没必要那么笨拙地一个一个去检验，我们采用一种类似素数筛地方法，将不符合要求的数全部筛去。 以左界限2为例，哪些数应该被筛去呢？由图容易理解，筛去2所在的基址加上2的倍数所构成的下标对应的元素就好了。 3也同理：筛去3所在的基址加上3的倍数所构成的下标对应的元素就好了。 那循环到哪是个头呢？其实很简单，就是基址+倍数>右边界的时候就可以停了。 完整代码如下： 数组的大小开区间的长度，要记得加上1 双重for循环完成标记 最后统计那些没有被标记到的元素。
好懂吧 <_>
这里的思维方式，其实是把时空难以解决的问题简单化，利用“基址+偏移”的思想来将原问题等价转换。
喜欢我的话，就给我点个赞吧
欢迎关注数构算法Wechat公众号：Design of Algorithm
