## Prime numbers – Sieve of Eratosthenes

A **prime number** is a **natural number** with only two divisors: **1** and **itself**.

In this post we’re going to show how to find **prime numbers** using **Sieve of Eratosthenes** and explain how it works.

## How it works

- Create a boolean array for the numbers you want to verify.

We create an array with size greater by one to comfortably use index as underlying number. - Initially mark all numbers in the array as primes.
- Start sieving from the smallest prime number – 2.
- Mark as non primes all multiplies of the current prime.

Notice that we start the sieve from*i*i*, because all numbers below have been already sieved. For example, when removing multiplies of 5 we can start from 25, because all lower multiplies of 5 have been removed when 2 and 3 were processed –*5*2 = 2*5*and*5*3 = 3*5*. - Repeat with the next prime.

We don’t have to look for primes above*maxPrime*, because of reasoning in point 4.

void markComplexNumbers(boolean[] primes) { primes[0] = primes[1] = false; int maxPrime = (int) Math.sqrt(primes.length); for (int i = 2; i <= maxPrime; ++i) { if (primes[i]) { // remove all multiplies of this prime: for (int j = i*i; j < primes.length; j += i) { primes[j] = false; } } } }

## Properties of the Sieve of Eratosthenes

- time complexity is
**O(n log log n)** - memory complexity is
**O(n+1)** - works great for small (in mathematical sense ;-) ) prime numbers

## Complete example

package com.farenda.tutorials.algorithms.primes; import java.util.Arrays; public class Sieve { public static void main(String[] args) { boolean[] primes = findPrimes(101); printPrimes(primes); } public static boolean[] findPrimes(int to) { // +1 to have index and number with the same value: boolean[] primes = new boolean[to+1]; Arrays.fill(primes, true); markComplexNumbers(primes); return primes; } private static void markComplexNumbers(boolean[] primes) { primes[0] = primes[1] = false; int maxPrime = (int) Math.sqrt(primes.length); for (int i = 2; i <= maxPrime; ++i) { if (primes[i]) { // remove all multiplies of this prime: for (int j = i*i; j < primes.length; j += i) { primes[j] = false; } } } } private static void printPrimes(boolean[] primes) { for (int i = 2; i < primes.length; ++i) { if (primes[i]) { System.out.print(i + ", "); } } } }

The above code produces the following output:

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, 101,