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