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]