算法之 数论

质数

质数的定义：除了本身和1，不能被其他小于它的数整除，最小的质数是 2

求解质数的几种方法
法1，根据定义，直接求解

        def zhi(i):if i == 1:return Falsefor j in range(2,i):if i % j ==0:return Falsereturn True

法2：优化暴力的解法,判断的时候只用判断到根号n,因为你如果存在一个大于根号n的因子，那就说明会存在一个小于根号n的因子，所以就不用重新判断

def zhi(i):if n <= 1:return Falsefor i in range(2, int(math.sqrt(n)) + 1):if n % i == 0:return Falsereturn True

常用的素数筛：

埃氏筛

def eratosthenes_sieve(n):is_prime = [True] * (n + 1)  # 初始化所有数为质数is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数for i in range(2, int(n**0.5) + 1):  # 只需遍历到 sqrt(n)if is_prime[i]:  # 如果 i 是质数for j in range(i * i, n + 1, i):  # 标记 i 的所有倍数为合数is_prime[j] = Falseprimes = [i for i, prime in enumerate(is_prime) if prime]  # 提取所有质数return primes

欧式筛

def euler_sieve(n):is_prime = [True] * (n + 1)  # 初始化所有数为质数primes = []  # 存储筛选出的质数for i in range(2, n + 1):if is_prime[i]:primes.append(i)  # i 是质数，加入 primes 数组for p in primes:if i * p > n:break  # 超过范围，退出循环is_prime[i * p] = False  # 标记 i * p 为合数if i % p == 0: # 说明 p 是 i 的最小的质因数break  # 保证每个合数只被最小质因数筛掉return primes

判断质数

3115.质数的最大距离

3115.质数的最大距离

思路分析：采用双指针进行判断，这样可以快速求解

class Solution:def maximumPrimeDifference(self, nums: List[int]) -> int:# 策略，使用双指针，从两边进行遍历，如果发现是质数就停下来# 判断质数def zhi(i):if i == 1:return Falsefor j in range(2,i):if i % j ==0:return Falsereturn Truen = len(nums)# 双指针l,r = 0,n-1while not zhi(nums[l]):l+=1while not zhi(nums[r]):r-=1return r-l

质数筛选

204.计数质数

204.计数质数

思路分析：直接考虑使用欧式筛,注意题目是小于n的素数个数

class Solution:def countPrimes(self, n: int) -> int:# 两种做法，可以采用欧式筛def euler(m):isprime = [True]*(m+1) # 存储判断i是否是素数prime = []for i in range(2,m):# 如果是素数if isprime[i]:prime.append(i)for j in prime:if i*j > m:breakisprime[i*j] = Falseif i%j ==0:break # 确保每个数字只能被最小的质因数筛选return primereturn len(euler(n))

2761.和等于目标值的质数对

2761.和等于目标值的质数对

思路分析：首先使用欧拉筛进行筛选出小于等于n的素数的情况，然后使用双指针进行判断

class Solution:def findPrimePairs(self, n: int) -> List[List[int]]:# 先使用欧式筛进行预处理def euler(m):isprime = [True]*(m+1)prime = []for i in range(2,m+1):if isprime[i]:prime.append(i)for j in prime:if i*j > m:breakisprime[i*j] = Falseif i%j == 0:breakreturn primeprime = euler(n)# 还是采用双指针吧length = len(prime)l,r = 0,length-1ans = []while l<=r:if prime[l]+prime[r] < n:l+=1elif prime[l]+prime[r] == n:ans.append([prime[l],prime[r]])l+=1r-=1else:r-=1# 排序非递减排序ans.sort(key=lambda x : x[0])return ans

2521.数组乘积中的不同质因数数目

2521.数组乘积中的不同质因数数目

思路分析：通过不断的判断

class Solution:def distinctPrimeFactors(self, nums: List[int]) -> int:s = set()for x in nums:i = 2while i*i <=x:if x % i == 0:s.add(i)x //= iwhile x%i == 0:x//=i i+=1# 最后可能只剩下那个数直接加进去if x>1:s.add(x)return len(s)