南昌网站建设南昌吊车出租,个人网站 后台管理,linux wordpress 区别,只做旧房翻新的装修公司文章目录 质数判断质数3115.质数的最大距离 质数筛选204.计数质数2761.和等于目标值的质数对 2521.数组乘积中的不同质因数数目 质数 质数的定义#xff1a;除了本身和1#xff0c;不能被其他小于它的数整除#xff0c;最小的质数是 2 求解质数的几种方法 法1#xff0c;根… 文章目录 质数判断质数3115.质数的最大距离 质数筛选204.计数质数2761.和等于目标值的质数对 2521.数组乘积中的不同质因数数目 质数 质数的定义除了本身和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]):l1while not zhi(nums[r]):r-1return r-l
质数筛选
204.计数质数
204.计数质数 思路分析直接考虑使用欧式筛,注意题目是小于n的素数个数 class Solution:def countPrimes(self, n: int) - int:# 两种做法可以采用欧式筛def euler(m):isprime [True]*(m1) # 存储判断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]*(m1)prime []for i in range(2,m1):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 lr:if prime[l]prime[r] n:l1elif prime[l]prime[r] n:ans.append([prime[l],prime[r]])l1r-1else:r-1# 排序非递减排序ans.sort(keylambda 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 i1# 最后可能只剩下那个数直接加进去if x1:s.add(x)return len(s)
