板子
1. 暴力
public List<Integer> ps(int num){
ArrayList<Integer> ans = new ArrayList<>();
if(num<=1){
return ans;
}
outer:for(int i=2;i<=num;i++){
for(int j=2;j<i;j++){
if(i%j==0){
continue outer;
}
}
ans.add(i);
}
return ans;
}
暴力筛的想法很简单,就是2到i-1每个数看一眼能不能整除,都不能就是素数。
2. 根号
public List<Integer> ps(int num) {
ArrayList<Integer> ans = new ArrayList<>();
if(num<=1){
return ans;
}
outer:for(int i=2;i<=num;i++){
int sqrt = (int) Math.sqrt(i);
for(int j=2;j<=sqrt;j++){
if(i%j==0){
continue outer;
}
}
ans.add(i);
}
return ans;
}
根号筛的想法稍微多一点,如果一个数能分解成n = p*q,那么p,q一定一个大于等于根号n,另一个小于等于根号n。因此检查到根号n就可以。
3. 埃氏筛
public List<Integer> ps(int num) {
ArrayList<Integer> ans = new ArrayList<>();
if(num<=1){
return ans;
}
boolean[] isPrime = new boolean[num+1];
Arrays.fill(isPrime,false);
for(int i=2;i<=num;i++){
// still not marked as a prime
if(!isPrime[i]){
ans.add(i);
// mark k*i,k>=2,k∈N*
for(int k=2;k*i<=num;k++){
isPrime[k*i]=true;
}
}
}
return ans;
}
全名埃拉托色尼筛。当一个数确定是素数,那么它的1、2、3、4、5……倍一定都是合数,因此简历标记数组isPrime。每次循环检查标记,若为True那么置入结果列表。同时把他的倍数(直到边界)全部置为False。从数学角度可以证明,埃氏筛的复杂度是O(nloglogn)
4. 欧拉筛
public List<Integer> ps(int num) {
ArrayList<Integer> ans = new ArrayList<>();
if(num<=1){
return ans;
}
boolean[] isPrime = new boolean[num+1];
Arrays.fill(isPrime,false);
for(int i=2;i<=num;i++){
if(!isPrime[i]) {
ans.add(i);
}
for (int j = 0; (j < ans.size()) && (ans.get(j) * i <= num); j++) {
isPrime[ans.get(j) * i] = true;
}
}
return ans;
}
埃筛的缺点是会有重复标记。比如2,3都是素数。那么2会标记一次6,3也会标记一次6,造成冗余。
欧拉筛在此基础上进一步优化,一个合数必定由多个素数组合而成。那么每次我们用已有素数和当前数组合,标记isPrime,可以使得isPrime中的每个数访问且仅访问一次。时间复杂度O(n)。
1. LC 3326 使数组非递减的最少除法操作次数
VP周赛420 T3。
一开始我给了个写起来简单但是跑起来很慢的解。首先因为结果数组非递减,因此最后那个数就是最大的。因此我们直接倒着开,从倒数第二个数开始往前走。如果当前数比后面一个数大,那么从2开始尝试寻找其最小因数。找到最小因数相当于除以了最大因数(真)。这个范围其实是在[2,nums[i+1]]的,并不用找到根号,这是因为如果你找不到不比后一个数大的因子那么就可以返回-1了。
class Solution:
def minOperations(self, nums: List[int]) -> int:
cnt = 0
for i in range(len(nums)-2,-1,-1):
if nums[i]>nums[i+1]:
for j in range(2,nums[i+1]+1):
if nums[i]%j==0:
nums[i] = j
cnt += 1
break
if nums[i]>nums[i+1]:
return -1
return cnt
然后这个解法跑了个6100ms,压线过了。后来发现其实可以预处理里面for j那段for loop。我们想找某个数最小因子是谁。不就相当于在欧拉筛里面看是哪个因子把他标记掉的嘛。如果这个数本身是素数,那么令minPrime[x] = -1即可。随后在循环中查询minPrime[nums[i]],如果为-1,或者比nums[i+1]大,那么返回-1,否则计数。
这题如果改成除以一个因子(不一定最大),那就比较难了。
def Euler_Prime_Sieve(mx:int)->List[int]:
minPrime = [-1 for _ in range(mx+1)]
primes = []
is_Prime = [True for _ in range(mx+1)]
for i in range(2,mx+1):
if is_Prime[i]:
primes.append(i)
for k in primes:
if i*k > mx:
break
is_Prime[i*k] = False
minPrime[i*k] = k
return minPrime
mp = Euler_Prime_Sieve(int(1e6))
class Solution:
def minOperations(self, nums: List[int]) -> int:
cnt = 0
for i in range(len(nums)-2,-1,-1):
if nums[i]>nums[i+1]:
if mp[nums[i]] == -1 or mp[nums[i]]>nums[i+1]:
return -1
nums[i] = mp[nums[i]]
cnt += 1
return cnt
时间复杂度:
- 预处理O(k),k为数组最大值
- 倒序遍历O(n),查询预处理过了O(1)
总体O(n+k)。