Skip to content

Instantly share code, notes, and snippets.

@gtke
Created September 10, 2012 18:40
Show Gist options
  • Select an option

  • Save gtke/3692820 to your computer and use it in GitHub Desktop.

Select an option

Save gtke/3692820 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes - Algorithm that generates prime numbers
import java.util.Scanner;
public class Eratosthenes {
/**
* Sieve of Eratosthenes.
* Generates prime numbers.
* You can find more about the algorithm here:
* http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
* @author gtkesh
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
int i=0,j=0;
//reading number 'n' from the user
int n = input.nextInt();
int [] arr = new int[n+1];
//filling array with numbers from 2 to n
for(i=2; i<=n; i++){
arr[i] = i;
}
//here goes the algorithm implementation
for(i=2; i<=n; i++){
for(j=i+1; j<=n; j++){
if(arr[j] % i == 0 && arr[j] > 0){
arr[j] = -1;
}
}
}
//printing values
for(i=2; i<=n; i++){
if(arr[i]>0){
System.out.print(arr[i]+ ",");
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment