愿此后再无WA：全心备战蓝桥杯，博客文章质量或将下降
想说
大家好，我叫@愿不了WA，你们可以叫我小A，也可以叫我圆圆，一个阳光帅气的小伙子，对算法领域比较感兴趣。如果我的文章对您有用，请继续关注，让我们共同进步！
对不起大家，现在距离蓝桥杯比赛还有不到一个月的时间了，我暂时改变了计划，转而全力备战蓝桥比赛，因为这个省对我来说太重要了，也我最后的机会。如果你想得到的话，我肯定会少花很多时间在博客上，而且也会导致博文质量明显下降。我想向大家道歉。
这些天我真的很开心。很高兴在博客上认识了一群志同道合的兄弟姐妹。没有你们的支持和鼓励，我不可能坚持下来。因为有你，我才能走得更远☀️☀️熬过去这段时间我一定会回来的，我爱你❤️❤️
吐槽
数论真是深不可测啊……还好我遇到的比较早。如果我在考试的时候遇到它，我就死定了。幸运的是，我的好朋友杨志哥发表了一篇文章，读后我学到了很多东西。不幸的是，它是用C++编写的，所以读起来有点不舒服。想看的朋友可以点击这里。
因式分解质因数
问题描述
求区间 [a,b] 中所有整数的质因数分解。
进入
输入两个整数a、b。
2<=a<=b<=10000
输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
分析
题输出有点难受，不过也是蓝桥VIP测试题，凑合着吧。
什么是主要因素？
数论中的质因数（或质因数）是指能整除给定正整数的质数。根据算术基本定理，每个正整数都可以唯一地表示为其素因子的乘积，无论排列顺序如何。两个没有共同质因数的正整数称为互质。
因此，如果一个数没有其他素因数，那么它的素因数就是它本身。
既然一个数可以用一个或几个质因数来表示，那么我们就可以从小到大遍历这个数。如果遇到质因数，我们就继续除它，直到不能再除为止（直到有小数）。向下。除法完成后，这个数就和刚才的质因数没有任何关系了。然后找到下一个素因数，重复上述步骤，直到这个数被除掉只剩下1为止。前面分离出来的才是首要因素。例如，客厅的桌子上有一个大蛋糕。小明饿了，就吃一口，然后再吃一口。当小明吃不下饭的时候，他才进房间。这时候馅饼少了一部分，而小明已经吃饱了，所以小明就不会再吃了。这时小明的爸爸看到了，因为饿了，就把馅饼吃了。等他吃饱了，如果还有的话，他妈妈可能会来吃等等。
现在我们只需要找到这些素因子，然后记录它们的数量，最后输出它们。
代码
def divide(n):
i = 2
while n != 1:
if n % i == 0:
s = 0
while n != 1 and n % i == 0:
s += 1
n /= i
dic[i] = s
i += 1
n,m = map(int,input().split())
for r in range(n,m+1):
dic = {}
divide(r)
res = ""
print(f'{r}=',end='')
for i in dic:
for j in range(dic[i]):
res += f"{i}*"
print(res[:-1])
小O素数
想法
要查找素数，您可以使用艾利希筛法。每找到一个素数，就遍历一次数组，去掉素数的倍数，重复这个步骤。然后就可以得到素数的个数了。借用杨志的一张图。
代码
def is_prime(n):
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3,int(n**0.5)+1,2):
if n % i == 0:
return False
return True
for _ in range(6):
n, m = map(int,input().split())
nums = [i for i in range(n,m+1)]
result = 0
for i in range(m-n+1):
if nums[i]:
result += 1
for j in range(i,m-n+1,nums[i]):
nums[j] = 0
# print(nums)
print(result)
阶乘除数问题
分析
咳咳，这是全国赛题。我们首先需要了解如何找到正因数。我们来看看杨志小凯整理的文章。非常好。
你必须了解如何求除数和除数之和，剩下的就很简单了。
我们只要遍历1到100，记录所有素因数的个数，最后用上面的公式输出即可。
代码
def prime_factor(n):
i = 2
while n != 1:
if n % i == 0:
s = 0
while n != 1 and n % i == 0:
n /= i
s += 1
if i in dic:
dic[i] += s
else:
dic[i] = s
i += 1
dic = {}
for i in range(1,101):
prime_factor(i)
res = 1
for i in dic.values():
res *= i+1
print(res)
评价
分析
这是一道全国竞赛题。如果你知道通过素因数可以求出正因数，并且知道如何求素因数的个数，那么这道题就会变得容易了。也就是遍历所有的数字并得到它们的所有素因数。和数，最后应用公式来求解。如果是100，则返回结果。不是很清楚的同学可以再看一下这张图。
代码
def prime(n):
mem = {}
for i in range(2,n+1):
if n % i == 0:
cnt = 0
while n != 1 and n % i == 0:
n //= i
cnt += 1
mem[i] = cnt
if n == 1:
res = 1
for i in mem:
res *= mem[i]+1
return res
for i in range(4,int(1e6)):
if prime(i) == 100:
print(i)
break
phper