100% in Java, O(N * log(log(N)) + M). Using https://codility.com/media/train/9-Sieve.pdf and prefix sum:

public int[] solution(int N, int[] P, int[] Q) {
    int M = P.length;
    int[] retVal = new int[M];
    int[] smallest = smallestPrimeThatDividesThisIndex(N);

    boolean[] isSemiPrime = new boolean[N + 1];
    for (int i = 0; i <= N; i++) {
        if (smallest[i] != 0 && smallest[i / smallest[i]] == 0) {
            isSemiPrime[i] = true;
        }
    }

    int[] prefixCount = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        prefixCount[i] = prefixCount[i - 1] + (isSemiPrime[i] ? 1 : 0);
    }

    for (int i = 0; i < M; i++) {
        retVal[i] = prefixCount[Q[i]] - prefixCount[P[i] - 1];
    }
    return retVal;
}

public static int[] smallestPrimeThatDividesThisIndex(int n) {
    int[] F = new int[n + 1];
    for (int i = 2; i * i <= n;i++) {
        if (F[i] == 0) {
            int k = i * i;
            while (k <= n) {
                if (F[k] == 0) {
                    F[k] = i;
                }
                k += i;
            }
        }
    }
    return F;
}