Java solution to Codility Prime Numbers Demo problem (PDF) (Lesson 11 – Sieve of Eratosthenes). The problem is to find all prime number up to N, for a given integer N.
The strategy is to:
- use boolean array to flag which indices are primes (left over as true)
- outer loop: check only numbers from 2 to the square root of N
- inner loop: start eliminating prime candidates starting from i^2 because lower numbers will have already been checked
- add all true indices from boolean array to java.util.List and convert to integer array
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
import java.util.ArrayList;
import java.util.List;
public class PrimesDemo {
public int[] solution(int N) {
//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();
return primes;
}
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson11.sieveoferatosthenes.PrimesDemo;
public class PrimesDemoTests {
private PrimesDemo solution;
@BeforeTest
public void setUp() {
solution = new PrimesDemo();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 2, new int [] { 2 } },
new Object [] { 3, new int [] { 2, 3 } },
new Object [] { 4, new int [] { 2, 3 } },
new Object [] { 5, new int [] { 2, 3, 5 } },
new Object [] { 10, new int [] { 2, 3, 5, 7 } },
new Object [] { 11, new int [] { 2, 3, 5, 7, 11 } },
new Object [] { 25, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23 } },
new Object [] { 36, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 } },
new Object [] { 49, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 } },
new Object [] { 64, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 } },
new Object [] { 66, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 } },
new Object [] { 67, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 } },
new Object [] { 68, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 } },
new Object [] { 69, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 } },
new Object [] { 70, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 } },
new Object [] { 80, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 } },
new Object [] { 90, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 } },
new Object [] { 100, new int [] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 } },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pInt, int [] pExpected) {
int [] actual = solution.solution(pInt);
Assert.assertEquals(actual.length, pExpected.length);
for(int i=0; i<actual.length; i++) {
Assert.assertEquals(actual[i], pExpected[i]);
}
}
}