阅读量:0
1. 解题思路
这一题的话关键就是想明白所谓的special number，事实上就是质数的平方数，因此，我们可以完全用求质数的方法来提前算出所有的special number，然后我们要做的就是找一下对应的边界范围内有多少的special number，然后剩下的就是我们所需要的答案了。
2. 代码实现
给出python代码实现如下：
def get_primes_square(): n = 10**5+1 status = [0 for _ in range(n)] ans = [] for i in range(2, n): if status[i] == 1: continue ans.append(i*i) for j in range(i, n, i): status[j] = 1 return ans PRIMES2 = get_primes_square() class Solution: def nonSpecialCount(self, l: int, r: int) -> int: def get_count(num): idx = bisect.bisect_right(PRIMES2, num) return idx return r-l+1-(get_count(r) - get_count(l-1)) 提交代码评测得到：耗时45ms，占用内存17.3MB。
