2025-03-13：统计不是特殊数字的数字数量。用go语言，给定两个正整数 l 和 r。对于一个数字 x，除了 x 自身以外的

福大大架构师每日一题

发布于 2025-03-13 13:47:42

7400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-13：统计不是特殊数字的数字数量。用go语言，给定两个正整数 l 和 r。对于一个数字 x，除了 x 自身以外的所有正因数称为 x 的真因数。

如果一个数字恰好有两个真因数，它被称为特殊数字。例如：

1.数字 4 是特殊数字，因为它的真因数是 1 和 2。

2.数字 6 不是特殊数字，因为它的真因数有 1、2 和 3。

你的任务是计算区间 [l, r] 内，非特殊数字的数量。

1 <= l <= r <= 1000000000。

输入： l = 4, r = 16。

输出： 11。

解释：

区间 [4, 16] 内的特殊数字为 4 和 9。

答案2025-03-13：

chatgpt[1]

题目来自leetcode3233。

大体步骤如下：

1.确定区间范围：给定两个正整数 l 和 r，表示区间范围为 [l, r]。

2.初始化计数器和存储数组：首先创建一个变量 res 用于统计非特殊数字的数量，初始化为区间内的数字总数 (r - l + 1)。然后创建一个长度为 n+1 的数组 v，用于标记每个数字是否为特殊数字。

3.遍历数字：从 2 开始遍历到 n，其中 n 是 r 的平方根。对每个数字 i，检查是否为特殊数字。

4.判断特殊数字：若 v[i] 为 0，表示数字 i 不是特殊数字。在 [l, r] 区间内，对于每个 i 的平方，若在区间内则该数字为特殊数字，res 减一。然后标记 i 的倍数为非特殊数字。

5.返回结果：返回剩余的非特殊数字数量即为答案。

6.时间复杂度：遍历数字范围为 [2, n]，n 为 r 的平方根，因此时间复杂度为 O(sqrt(r))。

7.空间复杂度：额外使用了长度为 n+1 的数组 v，因此空间复杂度为 O(sqrt(r))。

通过以上步骤可以对给定区间内的数字进行处理，找出非特殊数字的数量，最终计算时间复杂度为 O(sqrt(r))，空间复杂度为 O(sqrt(r))。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func nonSpecialCount(l int, r int)int {
    n := int(math.Sqrt(float64(r)))
    v := make([]int, n+1)
    res := r - l + 1
    for i := 2; i <= n; i++ {
        if v[i] == 0 {
            if i*i >= l && i*i <= r {
                res--
            }
            for j := i * 2; j <= n; j += i {
                v[j] = 1
            }
        }
    }
    return res
}

func main() {
    l := 4
    r := 16
    result := nonSpecialCount(l, r)
    fmt.Println(result) // 输出结果
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math

defnon_special_count(l, r):
    n = int(math.sqrt(r))
    v = [0] * (n + 1)
    res = r - l + 1

    for i inrange(2, n+1):
        if v[i] == 0:
            if i*i >= l and i*i <= r:
                res -= 1
            for j inrange(i*2, n+1, i):
                v[j] = 1

    return res

l = 4
r = 16
result = non_special_count(l, r)
print(result)  # 输出结果