Count the semiprime numbers in the given range [a..b]

Question

I am solving Codility problem CountSemiprimes: Count the semiprime numbers in the given range [a..b].

Task description

A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.

A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

You are given two non-empty arrays P and Q, each consisting of M integers. These arrays represent queries about the number of semiprimes within specified ranges.

Query K requires you to find the number of semiprimes within the range (P[K], Q[K]), where 1 ≤ P[K] ≤ Q[K] ≤ N.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..50,000];
• M is an integer within the range [1..30,000];
• each element of arrays P, Q is an integer within the range [1..N]; P[i] ≤ Q[i].

My solution

My current score is 66% and problem is preformance for large data set:

• large random, length = ~30,000
• all max ranges

Test says, that it should take about 2sec, but my solution takes over 7sec.

This is my current solution

class Solution {
    private static List<Integer> getPrimes(int max) {
        List<Integer> primes = new ArrayList<>(max / 2);

        for (int i = 0; i < max; i++)
            if (isPrime(i))
                primes.add(i);

        return primes;
    }

    private static boolean isPrime(int val) {
        if (val <= 1)
            return false;
        if (val <= 3)
            return true;

        for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
            if (val % i == 0)
                return false;

        return true;
    }

    private static boolean[] getSemiPrimes(int N) {
        List<Integer> primes = getPrimes(N);
        boolean[] semiPrimes = new boolean[N + 1];

        for (int i = 0; i < primes.size(); i++) {
            if (primes.get(i) > N)
                break;

            for (int j = i; j < primes.size(); j++) {
                if (primes.get(j) > N || N / primes.get(i) < primes.get(j))
                    break;

                int semiPrime = primes.get(i) * primes.get(j);

                if (semiPrime <= N)
                    semiPrimes[semiPrime] = true;
            }
        }

        return semiPrimes;
    }

    public static int[] solution(int N, int[] P, int[] Q) {
        boolean[] semiPrimes = getSemiPrimes(N);
        int[] res = new int[P.length];

        for (int i = 0; i < res.length; i++)
            for (int j = P[i]; j <= Q[i]; j++)
                if (semiPrimes[j])
                    res[i]++;

        return res;
    }
}

Any ideas about improving performance? My last one was to remove Set for holding semi-primes with array. It helped me to solve couple of performance tests.

Answer 1

A Java solution which scores 100% is as follow:

• Find the set of prime numbers which their products is not greater than N

• create semi-prime from them as a bit wise array of 0 and 1

• create a prefix sum of the semi-primes

• calculate the queries from P[i] to Q[i] in O(M)

The whole algorithm is of O(N * log(log(N)) + M) stated by the Codility's test result evaluation.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountSemiPrime {

    public static void main(String[] args) {
        int[] P = new int[] {1, 4, 16};
        int[] Q = new int[] {26, 10, 20};
        System.out.println( Arrays.toString( new CountSemiPrime().solution( 26, P, Q ) ) );
    }

    public int[] solution(int N, int[] P, int[] Q) {

        Integer[] primes = sieve(N/2+1);

        int[] temp = new int[N+1];
        for (int i = 0; i < primes.length; i++) {
            for (int j = 0; j < primes.length; j++) {
                int semiPrime = primes[i] * primes[j];
                if(semiPrime <= N)
                    temp[semiPrime] = 1;
            }
        }

        int[] prefix = new int[N+1];
        for (int i = 1; i < temp.length; i++) {
            prefix[i] = temp[i] + prefix[i-1];
        }

        int[] retVal = new int[P.length];
        for (int i = 0; i < retVal.length; i++) {
            retVal[i] = prefix[Q[i]] - prefix[P[i]-1];
        }

        return retVal; 
    }


    public Integer[] sieve(int n) {

        boolean[] temp = new boolean[n+1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = true;
        }
        temp[0] = temp[1] = false;

        int i = 2;
        while (i * i <= n) {
            removeProducts( temp, i );
            i++;
        }

        List<Integer> ret = new ArrayList<>();
        for (int j = 0; j < temp.length; j++) {
            if(temp[j])
                ret.add( j );
        }

        return ret.toArray( new Integer[ret.size()] );
    }

    private void removeProducts(boolean[] temp, int i) {
        for (int j = i*i; j < temp.length; j++) {
            if(temp[j] && j % i == 0) {
                temp[j] = false;
            }
        }
    }
}