1  import java.util.Scanner;
  2  
  3  public class SieveOfEratosthenes {
  4    public static void main(String[] args) {
  5      Scanner input = new Scanner(System.in);
  6      System.out.print("Find all prime numbers <= n, enter n: ");
  7      int n = input.nextInt();
  8      
  9      boolean[] primes = new boolean[n + 1]; // Prime number sieve
 10      
 11      // Initialize primes[i] to true
 12      for (int i = 0; i < primes.length; i++) {
 13        primes[i] = true; 
 14      }
 15      
 16      for (int k = 2; k <= n / k; k++) {
 17        if (primes[k]) {
 18          for (int i = k; i <= n / k; i++) {
 19            primes[k * i] = false; // k * i is not prime
 20          }
 21        }
 22      }
 23      
 24      final int NUMBER_PER_LINE = 10; // Display 10 per line
 25      int count = 0; // Count the number of prime numbers found so far
 26      // Print prime numbers
 27      for (int i = 2; i < primes.length; i++) {
 28        if (primes[i]) {
 29          count++;
 30          if (count % NUMBER_PER_LINE == 0) 
 31            System.out.printf("%7d\n", i);
 32          else
 33            System.out.printf("%7d", i);          
 34        }
 35      }
 36      
 37      System.out.println("\n" + count + 
 38        " prime(s) less than or equal to " + n);
 39    }
 40  }