For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation.
I would like to hear some suggestions for improvements, especially how to make it more efficient and readable (sometimes there are trade offs) and how to follow good Java conventions. Also, suggestions on issues from naming conventions to proper javadoc are welcome as well. I'm just trying to improve my programming skills.
Incidently, the sieveOfEratosthenes
method below is big O(?).
/**
* returns a boolean array for prime numbers
* @param max the maximum value to search for primes
* @return boolean array of integers with primes true
*/
public boolean[] sieveOfEratosthenes(int max){
boolean[] primeCandidates = new boolean[max]; //defaults to false
for(int i=2; i<max; i++ ){primeCandidates[i]=true;}
for(int i=2; i<Math.sqrt(max);i++){
if(primeCandidates[i] == true){
//all multiples of i*i, except i, are not primeCandidates
for(int j = i + i; j<max; j=j+i){
primeCandidates[j]=false;
}
}
}
return primeCandidates;
}
/**
* print the index number for all true in given array
* @param a boolean array
*/
public void printTrue(boolean[] arr){
for(int i=0; i<arr.length; i++){
if(arr[i]==true){
System.out.print(i + ", ");
}
}
}