Codility每周一课:P11.2?CountSemiprimes

作者 : 开心源码 本文共1977个字,预计阅读时间需要5分钟 发布时间: 2022-05-12 共260人阅读

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 CountSemiprimesdef 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,获取更多。

imageimage

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Codility每周一课:P11.2?CountSemiprimes

发表回复