Primes Demo – Codility – Solution

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

1
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
package com.codility.lesson11.sieveoferatosthenes;

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:


1
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
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.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]);
    }  
  }        
}