55 计算ID号

描述

我的微信ID是大写字母WHUT后面的数字是两个素数连在一起，大的在前，小的在后，如果我告诉你两数的乘积是多少，你能计算出我的ID号吗？‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬
如果输入一个[0-9]之间的数字，你能统计出从1开始到我ID中的数字的序列里，一共出现多少次这个数字吗？‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

输入格式

第一行输入ID中两个素数的乘积‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬
第二行输入一个[0-9]之间的数字‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

输出格式

第一行输出ID号‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬
第二行输出数字的次数

这个题目 可以分为以下几个模块：

1. 判定素数，定义函数 isPrime(n)，返回True或False
2. 找到输入数字的两个素数因子，定义函数 checkId(n)，返回整数ID
3. 统计输入数字出现的次数，定义函数 countnumber(ID,number)，返回次数
4. 输入输出部分

这里要用到判定素数的程序，注意return True的语句是在与for 匹配的else子句下面，是在for循环正常结束未执行到reutrn False时才会执行。

def isPrime(n):                           # 判断参数 n 是否为素数的函数
    if n <= 1:                            # 小于2的数字都不是素数
        return False
    elif n == 2:
        return True
    for i in range(3,int(n ** 0.5) + 1,2):   # 根据素数定义判定是否是素数，是素数返回1
        if n % i == 0:                     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数
            return False
    else:                                  # 若for循环未遇到return正常结束，则n是素数
        return True

检查ID时，可先判定这个素数是否为2与另一个素数相乘，这样再遍历其他素数时，可以设置步长为2，减少一半的计算量。当某个数num 和 n // num 都是素数，且n能被 num整除，则n // num 与num是一对结果，将其转为字符串拼接到一起返回即可。遇到return便会提前结束循环。

def checkId(n):
    if n % 2 == 0 and isPrime(n // 2):      #  如果n能被2整除，单独处理，提高效率
        return int(str(n // 2) + str(2))
    else:
        for num in range(3,n//2+1,2):       #  如果n不能被2整除，则两个素数不包括2，都是奇数
            if isPrime(num) and n % num == 0 and isPrime(n // num):  # isPrime(n // num)放在最后，利用短路效应，可以使大数的素数判定次数最少
                return int(str(n // num) + str(num))   # 返回值转字符串拼接后再转整数

当数字较小时，可以用列表推导式结合count()函数直接计算数字的次数，再用sum()函数求和便可得到总的次数。

def countnumber(ID,number):                 # 利用序列的count()函数
    return sum([str(x).count(str(number)) for x in range(1,ID+1)])

完整代码如下：

def isPrime(n):                           # 判断参数 n 是否为素数的函数
    if n <= 1:                            # 小于2的数字都不是素数
        return False
    elif n == 2:
        return True
    for i in range(3,int(n ** 0.5) + 1,2): # 根据素数定义判定是否是素数，是素数返回1
        if n % i == 0:                     # 从 2到n-1中如果存在一个数是i，使n 可以整除i，则n不是素数
            return False
    else:                                  # 若for循环未遇到return正常结束，则n是素数
        return True
def checkId(n):
    if n % 2 == 0 and isPrime(n // 2):      #  如果n能被2整除，单独处理，提高效率
        return int(str(n // 2) + str(2))
    else:
        for num in range(3,n//2+1,2):       #  如果n不能被2整除，则两个素数不包括2，都是奇数
            if isPrime(num) and n % num == 0 and isPrime(n // num):  # isPrime(n // num)放在最后，利用短路效应，可以使大数的素数判定次数最少
                return int(str(n // num) + str(num))   # 返回值转字符串拼接后再转整数
def countnumber(ID,number):                 # 利用序列的count()函数
    return sum([str(x).count(str(number)) for x in range(1,ID+1)])
if __name__ == '__main__':
    n = int(input())                        # 输入ID,整数，保证是两个素数的积
    number = int(input())                   # 输入0-9之间的一个数字
    ID = checkId(n)
    countNumber = countnumber(ID,number)    # 统计 number的个数
    print('WHUT' + str(ID))
    print(countNumber)

当数字较大时，统计次数销较大，需要优化算法，可用以下方法统计次数，具体原理参考这篇博客：

def countnumber(n,num):
    m, countnum = 1, 0
    while n//m > 0:
        high, mod = divmod(n, m*10)
        curNum, low = divmod(mod, m)
        if curNum > num:
            countnum += high*m + m
        elif curNum == num:
            countnum += high*m + low + 1
        else:
            countnum+= high*m
        m = m*10
    return countnum