CountSemiprimes – Codility – Solution

Java solution to Codility CountSemiprimes problem (Lesson 11 – Sieve of Eratosthenes) which scored 55%. The problem is to count the semiprime numbers in the given range [a..b].

The strategy is similar to the Primes Demo problem.

References

Solution to Count-Semiprimes (Code Says)

How to convert List<Integer> to int[] in Java (Stack Overflow)

[cc lang="java" escaped="true"]
package com.codility.lesson11.sieveoferatosthenes;

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

public class CountSemiprimes {
	public int[] solution(int N, int[] P, int[] Q) {
		//make size N+1 so will have direct mapping from array index
		boolean [] arePrimes = new boolean[N+1];

		arePrimes[0] = false; //0 is never prime
		arePrimes[1] = false; //1 is never prime
		for(int i=2; i<arePrimes.length; i++) {
			arePrimes[i] = true;
		}

		int nSquareRoot = (int) Math.sqrt(N);
		for(int i=2; i<=nSquareRoot; i++) {
			if(arePrimes[i]) {
				//start checking from i^2 because lower numbers will have already been checked
				//keep checking very multiple of i
				for(int j=i*i; j<=N; j+=i) {
					arePrimes[j] = false;
				}
			}
		}

		List primesList = new ArrayList();
		for(int i=2; i<arePrimes.length; i++) { if(arePrimes[i]) { primesList.add(i); } } //https://stackoverflow.com/questions/960431/how-to-convert-listinteger-to-int-in-java int[] primes = primesList.stream().mapToInt(i->i).toArray();

		int [] semiPrimes = new int[N + 1];	

		//populate semi primes set in order
		//reference: https://codesays.com/2014/solution-to-count-semiprimes-by-codility/
		for(int i=0; i<primes.length-1; i++) { if(primes[i] * primes[i] > N) {
				continue;
			}
			semiPrimes[primes[i]*primes[i]] = 1;  //square of the prime
			for(int j=i+1; j<primes.length; j++) { if(primes[i] * primes[j] > N) {
					break; //semi primes are larger than N so can stop calculating them
				}
				semiPrimes[primes[i]*primes[j]] = 1;
			}
		}
		
		for(int i=1; i<semiPrimes.length; i++) {
			semiPrimes[i] += semiPrimes[i-1];
		}
		
		int [] results = new int[P.length];
		for(int i=0; i<P.length; i++) {
			results[i] = semiPrimes[Q[i]] - semiPrimes[P[i] - 1];
		}
		return results;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson11.sieveoferatosthenes;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson11.sieveoferatosthenes.CountSemiprimes;

public class CountSemiprimesTests {
	private CountSemiprimes solution;
	
	@BeforeTest
	public void setUp() {
		solution = new CountSemiprimes();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] { 26, new int [] { 1, 4, 16 }, new int [] { 26, 10, 20 }, new int [] { 10, 4, 0 } },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int pInt, int [] pP, int [] pQ, int [] pExpected) {			
		int [] actual = solution.solution(pInt, pP, pQ);		
		Assert.assertEquals(actual.length, pExpected.length);		
		for(int i=0; i<actual.length; i++) {		
			Assert.assertEquals(actual[i], pExpected[i]);	
		}		
	}
}
[/cc]