“这些事儿在熟练之后，也许就像喝口水一样平淡，但却能给初学者带来巨大的快乐，我一直觉得，能否始终保持如初学者般的热情、专注，决定了在做某件事时能走多远，能做多好。” 该系列文章由python编写，所刷题目共三个来源：之前没做出来的 ；Leetcode中等，困难难度题目； 周赛题目；某个专题的经典题目，所有代码已AC。每日1-3道，随缘剖析，希望风雨无阻，作为勉励自己坚持刷题的记录。
204. 计数质数
枚举不再给出，最大问题在于没有考虑到数与数的关联性。
这里想学习一下【埃及筛（厄拉多塞筛法）】：
考虑x是质数，则其倍数2x，3x…一定不是质数。可以直接从 x⋅x 开始标记，因为 2x,3x… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。
class Solution:
def countPrimes(self, n: int) -> int:
# 从2开始检查，检查到n-1（小于等于就检查到n了）
isprime = [1 for i in range(0,n)]
if len(isprime)<=1:
return 0
isprime[0]=isprime[1]=0
for i in range(2,n):
if isprime[i]:
for j in range(i*i,n,i):
isprime[j]=0
return sum(isprime)
【线性筛】的做法更加高级，为了消除埃及筛中的冗余操作：
比如45会被3和5两个数同时标记，我们期望 O ( n ) O(n) O(n) 的复杂度，也就是每个数只被判定一次。根据《算术基本定理》：【每一个合数都可以以唯一形式被写成质数的乘积】。换言之，多个质数的乘积只能组成唯一的合数。不再标记 x 的所有倍数，而只标记质数集合中的数与 x 相乘的数。对于多个质数相乘的问题，不仅仅对质数进行合数标记，而是对每个数都进行，譬如 8 = 4 ∗ 2 8=4*2 8=4∗2 中4是不能被忽略的。每次标记时标记至 x m o d p r i m e s i = = 0 x mod primes_i==0 xmodprimesi==0，因为如果x可以整除某个质数，那么对于合数 x ∗ p r i m e s i = x / p r i m e s i ∗ p r i m e s i + 1 x * primes_i = x/primes_i * primes_{i+1} x∗primesi=x/primesi∗primesi+1，即后面一定存在一个更大的数使得其被标记。另一个博主的介绍中说目的是【用最小的质因子把他筛掉】。
class Solution:
def countPrimes(self, n: int) -> int:
# 从2开始检查，检查到n-1（小于等于就检查到n了）
isprime = [1 for i in range(0, n)]
if len(isprime) <= 1:
return 0
isprime[0] = isprime[1] = 0
primes = []
for i in range(2, n):
if isprime[i]:
primes.append(i)
for j in primes:
if j*i < n :
isprime[i*j] = 0
else:
break
# 必须先加入再退出
# 4 = 2*2
if i % j == 0:
break
return sum(isprime)
聪明的燕姿
题意是给出一个数 S ,求约数和等于 S 的所有数。
这里有个定理：
第一次接触比较难懂，举个例子：
360
=
2
3
×
3
2
×
5
360=2^3×3^2×5
360=23×32×5 ，其约数和为
(
1
+
2
1
+
2
2
+
2
3
)
×
(
1
+
3
1
+
3
2
)
×
(
1
+
5
1
)
(1+2^1+2^2+2^3)×(1+3^1+3^2)×(1+5^1)
(1+21+22+23)×(1+31+32)×(1+51)。
我们可以通过枚举（会超时）的方法检查每个数，也可以通过搜索的方法进行分解：
若当前数可表示成一个并未搜索过的质数与1的和，则之前搜索过的数与这个质数的乘积符合题意。对于每一个未被搜索过且平方小于当前数的质数，则枚举所有可能符合题意的ai 进行递归搜索。
实在没写出来，代码为这个博主的链接：
#include#include #include #include using namespace std; #define N 100000 int p[N+5],cnt,s,ans,num[N+5]; bool flag[N+5]; void getprime() { for(int i=2;i<=N;i++) { if(!flag[i]) p[++cnt]=i; for(int j=1; i*p[j]<=N; j++) { flag[i*p[j]]=1; if(i%p[j]==0) break; } } } bool isprime(int x) { if(x==1) return false; if(x<=N) return !flag[x]; for(int i=1;p[i]*p[i]<=x;i++) if(x%p[i]==0) return false; return true; } void dfs(int last,int now,int tot) { // now->summ, tot->left, last->pos if(tot==1){ num[++ans]=now; return; } if(tot-1>p[last]&&isprime(tot-1)) num[++ans]=now*(tot-1); for(int i=last+1; p[i]*p[i]<=tot; i++) for(int tnum=p[i]+1,t=p[i]; tnum<=tot; t*=p[i],tnum+=t) if(tot%tnum==0) dfs(i,now*t,tot/tnum); } int main() { getprime(); while(scanf("%d",&s)!=EOF) { ans=0; dfs(0,1,s); cout<
