3233.统计不是特殊数字的数字数量

链接：3233.统计不是特殊数字的数字数量
难度：Medium
标签：数组、数学、数论
简介：返回区间 [l, r] 内 不是 特殊数字 的数字数量。

题解 1 - python

• 编辑时间：2024-11-22
• 执行用时：253ms
• 内存消耗：16.86MB
• 编程语言：python
• 解法介绍：枚举素数，只有素数的乘积才是特殊数字

def get_primes(n: int) -> int:
    arr = [True] * n
    arr[0] = arr[1] = False
    for i in range(2, n):
        if arr[i]:
            j = 2
            while i * j < n:
                arr[i * j] = False
                j += 1
    return arr
primes = get_primes(10 ** 5)
class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        num = 2
        res = 0
        while num ** 2 <= r:
            if num ** 2 >= l and primes[num]:
                res += 1
            num += 1
        return r - l + 1 - res