Codility & Intercom: Sieve of Eratosthenes

Last months have been trying to seek a career change. Among different job interviews and screenings I got to know also Intercom. It left an awesome and bitter experience. I did manage to go to the on-site interview but I did not get an offer (sigh)… but that story would belong to another post.

I spent three days in Dublin and had a chance to make a second visit to the city. All is left from this trip are the souvenirs on the left, which I’ll get rid very quickly 🍻 (I could not find Programmer’s Tears whiskey), and the preparation with Codility Lessons. These lessons consist in various algorithm solving problems which in my case helped me a lot to polish some CS algorithm concepts. I solved all ‘Painless’ and most of ‘Respectable’ ones by myself, and noticed that in particular the solution of two problems could not be found online. So I just wanted to publish my solution to the problems of Sieve of Eratosthenes lesson. Unfortunately I cannot post the problems because they are subject of copyright by Codility. Both solutions get 100% score on correctness and performance. Please find the spartan explanation as comments between source code lines.

CountSemiprimes

class Solution {
    public int[] solution(int N, int[] P, int[] Q) {
        //the first semi prime is number 4
        if (N <= 3){
            return new int[1];
        }
        // build the sieve of primes up to N/2. Since
        // the smallest prime is 2, we cannot consider
        // primes bigger than N/2 because the product 
        // with 2 would result bigger than N.
        boolean[] primes = new boolean[N/2 + 1];
        for (int i = 0;i <= N / 2;i++){primes[i] = true;}
        primes[0] = false;
        primes[1] = false;
        int i = 2;
        
        while (i * i <= N / 2){
            if (!primes[i]){
                i++;
                continue;
            }
            int k = i * i;
            while(k <= N / 2){
                primes[k] = false;
                k += i;
            }
            i++;
        }

        // build another sieve for semi primes now
        boolean[] semiPrimes = new boolean[N + 1];

        for (int j = 1; j <= N/2; j++){
            if (primes[j]){
                int k = j;
                // be aware here, the product may overflow
                // resulting in a negative number that passes
                // the check to be smaller than N
                long product = (long)k * j;
                while(product <= N){
                    if (primes[k]){
                        semiPrimes[j*k] = true;
                        } 
                    k++;
                    product = (long)k * j;
                }
            }
        }
        //use prefix sum to count the semi primes
        //in the required queries.
        int[] prefix_sum = new int[N + 1];
        
        int sum = 0;
        for (int j = 0; j <= N;j++){
            if (semiPrimes[j]){ sum++; }
            prefix_sum[j] = sum;
        }
        int[] result = new int[P.length];
        for (int j = 0; j < P.length; j++){
            result[j] = prefix_sum[Q[j]] - prefix_sum[P[j]-1];
        }
        return result;
    }
}

CountNonDivisible

class Solution {
    public int[] solution(int[] A) {
        //each element A is within the range [1..2 * N]
        int[] factors = new int[A.length * 2 + 1];
        
        //count how many times each factor appear
        for (int i = 0;i < A.length; i++){
            factors[A[i]]++;
        }
        
        //build a sieve which saves all the common
        //multiples smaller than 2 * N of the input factors 
        int multi[] = new int [factors.length];
        
        for (int i = 1;i < multi.length;i++){
            if (factors[i] == 0) 
                continue;
            int k = 1;
            long product = (long)i * k;
            while(product < multi.length){
                //we increase the number of multiples
                //by the number of factors in the input 
                //array
                multi[k * i] += factors[i];
                k++;
                product = (long)i * k;
            }
        }
        //for each input element the number of non divisors
        //is the difference of the total number of elements
        //and the number of times that element appears as a
        //multiple of other input elements
        int result[] = new int[A.length];
        for (int i = 0;i < A.length; i++){
            result[i] = A.length - multi[A[i]];
        }
        return result;
    }
}

Any suggestion is more than welcome! Happy coding!!!

Andi Palo