import java.util.Scanner;

public class SieveOfEratosthenes {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Znajduje wszystkie liczby pierwsze <= n. Podaj n: ");
    int n = input.nextInt();
    
    boolean[] primes = new boolean[n + 1]; // Sito do liczb pierwszych
    
    // Inicjowanie primes[i] wartością true
    for (int i = 0; i < primes.length; i++) {
      primes[i] = true; 
    }
    
    for (int k = 2; k <= n / k; k++) {
      if (primes[k]) {
        for (int i = k; i <= n / k; i++) {
          primes[k * i] = false; // k * i nie jest liczbą pierwszą
        }
      }
    }
    
    final int NUMBER_PER_LINE = 10; // Wyświetlanie 10 liczb w wierszu
    int count = 0; // Zliczanie znalezionych liczb pierwszych
    // Wyświetlanie liczb pierwszych
    for (int i = 2; i < primes.length; i++) {
      if (primes[i]) {
        count++;
        if (count % NUMBER_PER_LINE == 0) 
          System.out.printf("%7d\n", i);
        else
          System.out.printf("%7d", i);          
      }
    }
    
    System.out.println("\n" + "Ile liczb pierwszych mniejszych lub równych " +
      n + "? " + count);
  }
}
