质数

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

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

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

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

def zhi(i):
	    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return 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] = False

    primes = [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 False
            for j in range(2,i):
                if i % j ==0:
                    return False
            return True
        n = len(nums)
        # 双指针
        l,r = 0,n-1
        while not zhi(nums[l]):
            l+=1
        while not zhi(nums[r]):
            r-=1
        return 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:
                        break
                    isprime[i*j] = False
                    if i%j ==0:
                        break # 确保每个数字只能被最小的质因数筛选
            return prime
        return 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:
                        break
                    isprime[i*j] = False
                    if i%j == 0:
                        break
            return prime
        
        prime = euler(n)
        # 还是采用双指针吧
        length = len(prime)
        l,r = 0,length-1
        ans = []
        while l<=r:
            if prime[l]+prime[r] < n:
                l+=1
            elif prime[l]+prime[r] == n:
                ans.append([prime[l],prime[r]])
                l+=1
                r-=1
            else:
                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 = 2
            while i*i <=x:
                if x % i == 0:
                    s.add(i)
                    x //= i
                    while x%i == 0:
                        x//=i 
                i+=1
        # 最后可能只剩下那个数直接加进去
            if x>1:
                s.add(x)
        return len(s)