leetcode新年福利，本次周赛没有Hard难度的题目，然后我就第一次AK了~
总的来说不是很难，涉及到了三个算法，在此记录一下。
分解质因数
题目链接：6279. 数组乘积中的不同质因数数目
实际上本题就是求数组中每个元素的质因数，并扔到哈希表中进行去重。
所以唯一难点即是如何将一个数进行质因数分解。
方法：从2开始，如果该数可以整除2，那么就将该数除以2，再除以2，……直到无法整除之后，将除数2变成3，重复上述操作。
注意由于每一次操作都除掉了所有的因子，所以不用担心后续会将合数误判为质因数的情况，非常巧妙。
模板(Python)
n = NUM # 待分解的数
s = set() # 存储所有质因数的哈希表
x = n
i = 2
while i*i <= x:
while x%i == 0:
s.add(i)
x //= i
i += 1
埃氏筛
题目链接：6280. 范围内最接近的两个质数
初中就学过的简单算法。不再赘述。
模板(Python)
def sieve_of_eratosthenes(n): # 埃拉托色尼筛选法，返回小于等于n的素数
primes = [True] * (n + 1) # 范围0到n的列表
p = 2 # 这是最小的素数
while p * p <= n: # 一直筛到sqrt(n)就行了
if primes[p]: # 如果没被筛，一定是素数
for i in range(p * 2, n + 1, p): # 筛掉它的倍数即可
primes[i] = False
p += 1
primes = [element for element in range(2, n + 1) if primes[element]] # 得到所有小于等于n的素数
return primes
欧拉筛
埃氏筛的缺点在于一个数可能会被筛多次的情况，在数据范围n较大时可能具有较高的开销。因此，另一种欧拉筛(又称线性筛)应运而出。其思想是：每一个合数都只被它的lpf(最小质因数)筛掉。
因此，在筛的过程中，如果一个数被划掉了，即该数是合数，那么只需要划掉(或者划至，下面的模板就是划至)其lpf乘以自身的那个数；如果该数是质数，即尚未被筛，那么就全都要划。
模板(Python)
def euler_flag_prime(n):
# 欧拉线性筛素数，返回小于等于n的所有素数
flag = [False for _ in range(n + 1)]
prime_numbers = []
for num in range(2, n + 1):
if not flag[num]:
prime_numbers.append(num)
for prime in prime_numbers:
if num * prime > n:
break
flag[num * prime] = True
if num % prime == 0:
break
return prime_numbers
开年AK，开心。也希望自己2023年的Resolutions都能实现，每件事情都能持之以恒地做下去！