criskgl
7/22/2019 - 10:23 AM

Sieve of Eratostenes (Prime Numbers)

Sieve of Eratostones

Implementation of a method that returns a list of the prime numbers up to a number given.

  • It first makes the list up to n
  • Then crossed out the values that can be divided by 2
  • Then picks the next non crossed number
  • Then crosses out the numbers that can be divided by the number that has just been picked
/*
*This example implements a method that returns
*a list of the prime numbers up to a number given
*/

import java.util.ArrayList;
import java.util.Arrays;

public class SieveEratostenes {

	public static void main(String[] args) {
		int primesUntil = 100;
		ArrayList<Integer> result = sieveOfEratostenes(primesUntil);
		System.out.println("The primes from 2 to "+primesUntil+" are: "+result.toString());
	}	
	
	//Parameter: max value for which we will check if its part of the list of primes
	static ArrayList<Integer> sieveOfEratostenes(int max){
		int[] init = new int[max];
		//Build array with values from 2 to max.
		for(int i = 0, value = 2; i < init.length; i++, value++){
			init[i] = value;
		}
		ArrayList<Integer> result = new ArrayList<Integer>();
		boolean[] crossedOut = new boolean[max];
		int index = 0;
		int pivot = init[index];
		crossedOut[index] = true;
		while(!allCrossedOut(crossedOut)){
			crossedOut[index] = true;
			//Cross out the values that are divisible by pivot
			for(int i = index + 1; i < init.length; i++){
				int evaluatedElem = init[i];
				if(evaluatedElem % pivot == 0){//Cross it out
					crossedOut[i] = true;
				}
			}
			//Find new pivot with the next value in the 
			//list that has not been crossed out yet
			for(int i = index+1; i < init.length; i++){
				if(crossedOut[i] == false){
					result.add(pivot);
					pivot = init[i];
					index = i;
					break;
				}
			}
		}
		
		return result;
	}
	//This methods checks if all values have been marked as true in an array
	static boolean allCrossedOut(boolean[] crossedOut){
		for(boolean b : crossedOut){
			if (b == false){
				return false;
			}
		}  
		return true;
	}

}