蓝桥杯第十一届国赛Python组试题C阶乘约数——唯一分解定理的应用

简介: 定义阶乘 n! = 1 × 2 × 3 × · · · × n。请问 100! (100 的阶乘)有多少个约数。

试题 C: 阶乘约数

问题描述

定义阶乘 n! = 1 × 2 × 3 × · · · × n。

请问 100! (100 的阶乘)有多少个约数。

思路

直接求100的阶乘数值之后再求所有的约数的方式不可取,时间需求太大,这里使用唯一分解定理。

唯一分解定理

2345_image_file_copy_7.jpg


简而言之就:


2345_image_file_copy_8.jpg

用在这里若想求出100!的所有质数所消耗时间也是非常大,这里求出逐个1-100内所有的质数个数,质数个数求和,最后再相乘即可。

题解

def jiechengyueshu2():
  # 哈希表 存放质数
    temp = {}
    # 求出100以内所有质数
    for i in range(2, 101):
        judge = True
        for j in range(2, floor(sqrt(i))+1):
            if i % j == 0:
                judge = False
        if judge:
            temp[i] = 1
    #  求出2-100所有的质数和
    for i in range(2, 101):
        index = i
        for key in temp.keys():
            while index % key == 0:
                index //= key
                temp[key] += 1
    ans = 1
    # print(temp)
    # 按照唯一分解定理规律,将所有质数之和相乘即可,这里没有每一项都+1,因为哈希表中每一项的初始值为1
    for i in temp.values():
        ans *= i
    print(ans)


目录
相关文章
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
629 3
|
Python
蓝桥杯练习题(一):Python组之入门训练题
这篇文章是关于蓝桥杯Python组的入门训练题,包括Fibonacci数列、圆的面积、序列求和和A+B问题的具体代码实现和样例输出。
636 0
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
1100 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
人工智能 Python
蓝桥杯练习题(四):Python组之历届试题三十题
关于蓝桥杯Python组历届试题的三十个练习题的总结,包括题目描述、输入输出格式、样例输入输出以及部分题目的解题思路和代码实现。
875 0
蓝桥杯练习题(四):Python组之历届试题三十题
|
Java
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
307 4
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(二):Python组之基础练习三十题
蓝桥杯Python编程练习题的集合,包含了三十个不同难度的编程题目,覆盖了基础语法、数据结构和算法等领域。
730 0
|
存储 算法 测试技术
第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用
第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用
361 1
|
Java
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
349 1
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
311 0
|
数据采集 机器学习/深度学习 人工智能
Python:现代编程的首选语言
Python:现代编程的首选语言
1942 102

推荐镜像

更多