课前测2-丑数-Toy模板网

这篇具有很好参考价值的文章主要介绍了课前测2-丑数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

课前测2-丑数

程序设计

程序分析

系列文章

课前测2-丑数

【问题描述】

丑数的定义是这样的——
一个数，如果它分解后的素因子最多只有2、3、5、7四种，这个数则称为“丑数”。比如，前20个丑数是：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27。
现在你的任务是：给你一个数，你能判断是否是丑数吗？

【输入形式】

输入数据的第一行首先是一个整数C，表示测试数据的个数，然后是C组数据，每组测试数据包含一个整数n(1 <= n <= 2^31-1)。

【输出形式】

对于每组测试数据，如果n是丑数，则请输出“ Yes”,否则，请输出“No”.

【样例输入】

3

12

385875

11

【样例输出】

Yes

Yes

No

程序设计

Python

n=int(input())
for i in range(n):
    x=int(input())
    while x%2==0:
        x=x//2
    while x%7==0:
        x=x//7
    while x%5==0:
        x=x//5
    while x%3==0:
        x=x//3
    if x==1:
        print("Yes")
    else:
        print("No")

程序分析

该程序实现了判断一个数是否为丑数的功能，下面对代码进行解析：
首先，读入一个整数 n，表示接下来有 n 个数需要判断是否为丑数。
然后，使用循环结构遍历 0 到 n-1 的所有整数，对于每个整数执行以下操作：
读入一个整数 x，并使用 while 循环结构，将 x 分别除以 2、7、5、3，直到不能整除为止。这是因为丑数只包含因子 2、3、5、7，因此如果 x 能够被 2、7、5、3 整除，则将其除以对应因子。这样，如果 x 最终等于 1，则说明它是丑数，否则不是。
根据上述判断结果，输出 Yes 或 No。
总体来说，该程序实现了对多个整数进行丑数判断的功能，时间复杂度为 O(n log x)，其中 x 为最大的输入整数，适用于处理中等规模数据。如果需要处理更大规模的数据，可以考虑使用动态规划等算法实现丑数判断，以提高效率。文章来源地址https://www.toymoban.com/news/detail-412426.html

系列文章

序号	文章目录	直达链接
1	课前测1-输入练习	https://want595.blog.csdn.net/article/details/130033711
2	课前测2-丑数	https://want595.blog.csdn.net/article/details/130033752
3	课前测3-字符三角形	https://want595.blog.csdn.net/article/details/130033778
4	课前测4-奋勇争先	https://want595.blog.csdn.net/article/details/130033832
5	课前测5-超级密码	https://want595.blog.csdn.net/article/details/130033877
6	求根号n下界	https://want595.blog.csdn.net/article/details/130033902
7	数据结构exp1_2学生成绩排序	https://want595.blog.csdn.net/article/details/130033978
8	十进制到八进制的转换	https://want595.blog.csdn.net/article/details/130034024
9	数据结构exp1_1(选择排序）	https://want595.blog.csdn.net/article/details/130034058