每周一课：L11 Sieve of Eratosthenes(1

11.png

P11.2 CountSemiprimes

Count the semiprime numbers in the given range [a, b].

P11.2 半素数个数
计算区间[a, b]中的半素数的个数

只有1与该数本身这两个正因数的数称为素数。前6个质数分别是2、3、5、7、11和13。半素数是两个(可以相同)素数的乘积。前10个半素数分别是4，6，9，10，14，15，21，22，25，26。

有两个非空数组P和Q，每个数组由M个整数组成。在这些数组的元素组成的指定的区间内寻找半素数。对于K次查询，也就是在区间[P[K]，Q[K]]内寻找半素数，其中1 ≤ P[K] ≤ Q[K] ≤ N。

例如，给定整数N=26、以及数组P，Q，其中：
P[0]=1，P[1]=4，P[2]=16；Q[0]=26，Q[1]=10，Q[2]=20

这些区间中的半素数查询结果如下：
[1，26]中的半素数个数有10个；
[4，10]中的半素数有4个；
[16，20]中没有半素数，因此为0；

编写函数：

def solution(N, P, Q)

给定一个整数N和两个由M个整数组成的非空数组P和Q，则返回一个由M个元素组成的数组，其元素表示每个查询中半素数的个数。

例如，针对上面的示例，函数应返回值[10、4、0]。

假定：

1. N是区间[1，50000]内的整数；
2. M是区间[1，30000]内的整数；
3. 数组P，Q的每个元素都是区间[1，N]内的整数；
4. P[i] ≤ Q[i]；

• 解题思路

因为最终的每次查询，都需要用到半素数列表，因此需要把半素数列表先计算出来。

现在的问题是如何定义一个半素数，因为半素数是2个素数(可以相同)的乘积，1不是质数。因此半素数只能有3个，或者4个因子。只要因子数不符合，肯定不是。但是对于符合的也不一定全是，例如27的因子为(1, 3, 9, 27)， 125的因子为(1, 5, 25, 125)……。也就是对于素数的立方的情况，虽然也有4个因子，但是不满足条件。因此只要把这种情况去除掉就可以了。

得到半素数列表以后，需要得到每个数值以及前面数值中是半素数个数的字典，以及存储半素数的字典。接着就是判断区间内半素数的个数，如果区间开始值，恰好是半素数，则差值需要加1，不是的话，就是差值。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 11：Sieve of Eratosthenes
# P 11.2 CountSemiprimes


def solution(N, P, Q):
    """
    返回由数组P、Q的元素组成的区间内，不大于N的半素数的个数, 时间复杂度O(N * log(log(N)) + M)
    :param N: 半素数的最大值
    :param P: 数组
    :param Q: 数组
    :return: 每次查询,得到的半素数的个数
    """
    #  半素数只有3或4个因子，并且不能是素数的立方，例如(1, 3, 9, 27)(1, 5, 25, 125)这种情况
    #  首先计算出不大于N的半素数列表，是半素数的为其值，不是的为0
    semi_prime = []
    for i in range(1, N + 1):
        factor_count = 0
        sign = 0
        for j in range(1, int(i ** 0.5) + 1):
            if i % j == 0:
                factor_count += 1
                f = i / j
                if f != j:
                    if f == j ** 2:
                        sign = 1
                        semi_prime.append(0)
                        break
                    else:
                        factor_count += 1
            if factor_count > 4:
                sign = 1
                semi_prime.append(0)
                break
        if sign != 1:
            if factor_count >= 3:
                semi_prime.append(i)
            else:
                semi_prime.append(0)

    index_dict = {}  # 得出当前数值以及前面一共有几个半素数
    semi_dict = {}  # 如果是半素数，则添加到字典中
    count = 0
    for index, value in enumerate(semi_prime):
        if value != 0:
            count += 1
            index_dict[value] = count
            semi_dict[value] = 0
        else:
            index_dict[index + 1] = count

    result_list = []  # 开始计算，在指定区间内有几个半素数
    for i, j in zip(P, Q):
        if i in semi_dict:
            result_list.append(index_dict[j] - index_dict[i] + 1)
        else:
            result_list.append(index_dict[j] - index_dict[i])

    return result_list

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image