Leetcode 3233. Find the Count of Numbers Which Are Not Special

• Leetcode 3233. Find the Count of Numbers Which Are Not Special
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3233. Find the Count of Numbers Which Are Not Special

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。