codility 11-2 CountSemiprimes

本文主要是介绍codility 11-2 CountSemiprimes，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最近看到挺有意思的一题，原题链接：https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_semiprimes/

题目描述
质数是一个正整数X，它有两个不同的除数:1和X。最初的几个质数是2、3、5、7、11和13。
半质数(semiprime)是一个自然数，它是两个质数的乘积(不一定是不同的)。前几个半素数是4,6,9,10,14,15,21,22,25,26。

给定两个非空数组 P 和 Q，每个数组由 M 个整数组成。这些数组表示有关指定范围内半素数个数的查询，返回 [ P[k], Q[k] ] 左闭右闭区间半质数的个数，其中1≤ P [ K ] ≤ Q [ K ]≤ N。

例如：P = [1, 4, 16], Q = [26, 10, 20] , 返回 [10, 4, 0]。

P[0], Q[0] -->  [1, 26] 中间半质数有4,6,9,10,14,15,21,22,25,26, 共 10 个
P[1], Q[1] -->  [4, 10] 中间半质数有4,6,9,10, 共 4 个
P[2], Q[2] -->  [16, 20] 中间半质数共 0 个

思路与实现
由于1 ≤ P[K] ≤ Q[K] ≤ N，所以先存 0 到 N 每个数到当前数的半质数个数: dict = {数：到当前数的半质数个数}，这样对于每个 P[k] 到 Q[k] 区间，只需要计算dict[Q[k]] - dict[P[k]]，当 P[k] 为半质数时需要 +1。

如何求 0 到 N 每个数到当前数 x 的半质数个数，可以简单描述为 dict[x] = dict[x-1]+1 if x是半质数 else dict[x-1]。

然后问题来到如何求一个数 x 是否是半质数：将 x 拆成两个数的乘积，再判断这两个数是否都为质数。又因为将 x 拆成两个数的乘积，一定有一个数小于根号 x，所以只需要遍历到根号 x 来降低复杂度。

def solution(N, P, Q):
    res = []

    # 寻找N内半质数
    semiprime_dict = {}
    prime_nums = set()  # 存质数，不用重复判断，节省空间也可以不要
    for i in range(2, int(N**0.5)+1):
        # 不是质数
        if i not in prime_nums and not is_prime(i):
            continue
        prime_nums.add(i)
        for j in range(i, int(N/i)+1):
            if j not in prime_nums and not is_prime(j):
                continue
            # 如果i, j 都是质数
            prime_nums.add(j)
            # 半质数加入semiprime_dict中
            semiprime_dict[i*j] = 0

    # semiprime_dict={数：到当前数的半质数个数} 当前只有半质数，将 semiprime_dict 扩展到所有数
    # （实现的有点复杂
    semiprimes = sorted(semiprime_dict)  # 排序后的键值
    count = 0
    for x in semiprimes:   # 对于每个半质数，到当前的半质数个数
        count += 1 
        semiprime_dict[x] = count
    semiprime_dict[0] = 0  # 1，2，3都应该是0，加入0是解决P[i]=1的情况
    for x in range(1, N+1):		# 非半质数，到当前的半质数个数与前一个相同
        if x not in semiprime_dict:
            semiprime_dict[x] = semiprime_dict[x-1]
    
    # 找 P[i]-Q[i]之间semiprime_list的元素个数 O(M)
    for i in range(len(P)):
        count = semiprime_dict[Q[i]] - semiprime_dict[P[i]]
        if semiprime_dict[P[i]] > semiprime_dict[P[i]-1]:
            count += 1
        res.append(count)

    return res

# 判断质数
def is_prime(x):
    # 偶数一定不是质数
    if x != 2 and x % 2 == 0:
        return 0 
    # x 拆成两个数的乘积一定有一个小于根号x
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return 0

    return 1

这篇关于codility 11-2 CountSemiprimes的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！