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)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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]);
}
}
}