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

[cc lang="java" escaped="true"]
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;
	}
}
[/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.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]);	
		}		
	}					
}
[/cc]