# COZIE - Editorial

The sweetness factor is exactly the Euler totient function https://en.wikipedia.org/wiki/Euler%27s_totient_function.
If the prime factorization of n is p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} then we have:
\phi(n) = p_1^{e_1-1} (p_1-1) \cdot p_2^{e_2-1} (p_2-1) \cdots p_k^{e_k-1} (p_k-1)
For a prime p_i > 3, the value (p_i-1) is an even number greater than two so having a prime factor p_i > 3 implies that \phi(n) is not prime. A sweetness factor could be prime only for numbers of the form n = 2^a \cdot 3^b. We distinguish 3 cases:

1. \phi(n) = 2^{a} \cdot 3^{b-1} if a > 0, b > 0
2. \phi(n) = 3^{b-1} 2 if a = 0
3. \phi(n) = 2^{a-1} if b = 0

In the first case, primality of \phi(n) implies a=1, b=1 so n=6
In the second case, primality of \phi(n) implies b=1 so n=3
In the third case, primality of \phi(n) implies a=2 so n=4
So only 3, 4 and 6 have a prime sweetness factor.

Example of C++ solution:

#include <iostream>
#include <vector>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, Q;
cin >> N >> Q;
vector<int> a(N+1, 0);
for(int i = 1; i <= N; ++i) {
cin >> a[i];
if(a[i] == 3 || a[i] == 4 || a[i] == 6) a[i] = a[i-1]+1;
else a[i] = a[i-1];
}
while(Q--) {
int l, r;
cin >> l >> r;
cout << a[r] - a[l-1] << '\n';
}

return 0;
}