3896. Minimum Operations to Transform Array into Alternating Prime
You are given an integer array nums.
An array is considered alternating prime if:
- Elements at even indices (0-based) are prime numbers.
- Elements at odd indices are non-prime numbers.
In one operation, you may increment any element by 1.
Return the minimum number of operations required to transform nums into an alternating prime array.
A prime number is a natural number greater than 1 with only two factors, 1 and itself.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| vector<int> primes;
bool done = false;
class Solution {
void init() {
if(done) return;
int n = 2e5;
vector<int> sieve(n+1);
for(long long i = 2; i <= n; i++) {
if(sieve[i]) continue;
primes.push_back(i);
for(long long j = i * i; j <= n; j += i) sieve[j] = 1;
}
}
public:
int minOperations(vector<int>& nums) {
init();
int res = 0;
for(int i = 0; i < nums.size(); i++) {
int lb = lower_bound(primes.begin(), primes.end(),nums[i]) - begin(primes);
if(i&1) {
if(primes[lb] == nums[i]) res += (nums[i] == 2 ? 2 : 1);
} else {
res += primes[lb] - nums[i];
}
}
return res;
}
};
|
