# 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
```
123456789101112131415161718192021222324252627282930313233343536373839package 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]) {
}
}
//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:

```
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950package 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]);
}
}
}

```