# 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)

```
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556package 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;
}
}

```

TestNG test cases for this problem which all passed:

```
123456789101112131415161718192021222324252627282930313233package 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]);
}
}
}

```