蓝桥杯模拟题--约数的个数（约数和质因数的区别）

1.求一个数的约数及其个数

约数：约数是指能够整除一个整数的数。如果整数a除以整数的商正好是整数而没有余数，我们就说b是a的约数。例如，6可以被1，2，3，4整除，所以1、2、3、6都是6的约数。

用代码实现十分简单，只需一个for循环即可

# 以12为例
n=12
li=[]
for i in range(1,n+1):
    if n%i==0:
        li.append(i)
print(li)
print(len(li))

# [1, 2, 3, 4, 6, 12]
# 6

2.求一个数的质因数及其个数

质因数：质因数是指一个数的因数中，既是质数又是因数的数。也就是说，质因数是在约数的基础上，进一步限定为质数。例如，6=2*3,其中2和3是质数，所以2和3是6的质因数。

a=12
i=2
lis=[]
while i*i<=a:  # 减少不必要的判断
    while a%i==0: 
        lis.append(i)
        a//=i
    i+=1
if a>1:
    lis.append(a)
print(lis)
print(len(lis))

# [2, 2, 3]
# 3

3.蓝桥杯模拟题

测试数据如下：

393353 901440 123481 850930 423154 240461
373746 232926 396677 486579 744860 468782
941389 777714 992588 343292 385198 876426
483857 241899 544851 647930 772403 109929
882745 372491 877710 340000 659788 658675
296521 491295 609764 718967 842000 670302

 3.1 方法一

利用for循环依次遍历，代码简单，十分容易理解，但是面对众多数据时耗时长

nums, mx, key = [list(map(int, input().split())) for _ in range(6)], 0, 0

def g(n):
    li=[]
    for i in range(1,n+1):
        if n%i==0:
            li.append(i)
    return len(li)
for i in range(6):
    for j in range(6):
        ans=g(nums[i][j])
        if ans>mx:
            mx,key=ans,nums[i][j]
print(key)

# 901440

3.2 方法二

运用约数个数定理，显著提高程序运行速度，但不易理解

约数个数定理：约数个数等于不同的质因数的次数加一的累乘

nums, mx, key = [list(map(int, input().split())) for _ in range(6)], 0, 0

def f(n):
    i=2
    res=1
    while i*i<=n:
        c=1   # 因为是次数加1的累乘，首先定义次数为1
        while n%i==0:
            n=n//i
            c+=1  # 每得出一个质因数，其次数加1
        i += 1
        res*=c    # 次数加1的累乘

    if n>1:       # 若最后的数>1
        res*=2    # 其次数加1必为2
    return res

for i in range(6):
    for j in range(6):
        ans=f(nums[i][j])
        if ans>mx:
            mx,key=ans,nums[i][j]
print(key)

3.3 两种方法耗时对比

import time
nums, mx, key = [list(map(int, input().split())) for _ in range(6)], 0, 0
start1=time.time()
def g(n):
    li=[]
    for i in range(1,n+1):
        if n%i==0:
            li.append(i)
    return len(li)
for i in range(6):
    for j in range(6):
        ans=g(nums[i][j])
        if ans>mx:
            mx,key=ans,nums[i][j]
print(key)
end1=time.time()
print(f"方法一所用的时间{end1-start1}秒")

nums, mx, key = [list(map(int, input().split())) for _ in range(6)], 0, 0
start2=time.time()
def f(n):
    i=2
    res=1
    while i*i<=n:
        c=1
        while n%i==0:
            n=n//i
            c+=1
        i += 1
        res*=c
    if n>1:
        res*=2
    return res
for i in range(6):
    for j in range(6):
        ans=f(nums[i][j])
        if ans>mx:
            mx,key=ans,nums[i][j]
print(key)
end2=time.time()
print(f"方法二所用的时间{end2-start2}秒")



# 393353 901440 123481 850930 423154 240461
# 373746 232926 396677 486579 744860 468782
# 941389 777714 992588 343292 385198 876426
# 483857 241899 544851 647930 772403 109929
# 882745 372491 877710 340000 659788 658675
# 296521 491295 609764 718967 842000 670302
# 901440
# 方法一所用的时间0.5132265090942383秒
# 393353 901440 123481 850930 423154 240461
# 373746 232926 396677 486579 744860 468782
# 941389 777714 992588 343292 385198 876426
# 483857 241899 544851 647930 772403 109929
# 882745 372491 877710 340000 659788 658675
# 296521 491295 609764 718967 842000 670302
# 901440
# 方法二所用的时间0.0009989738464355469秒

明显看出方法一需要大约0.5秒，方法二只需要0.001秒，当面对更多的数据时，方法一耗时会更长