import java.util.Scanner;

public class EfficientPrimeNumbers {
  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();

    // Lista przechowująca liczby pierwsze
    java.util.List<Integer> list = 
      new java.util.ArrayList<>(); 

    final int NUMBER_PER_LINE = 10; // Po 10 liczb w wierszu
    int count = 0; // Zliczanie liczb pierwszych
    int number = 2; // Sprawdzana liczba
    int squareRoot = 1; // Służy do sprawdzania, czy number <= squareRoot

    System.out.println("Liczby pierwsze: \n");

    // Wielokrotne znajdowanie liczb pierwszych
    while (number <= n) {
      // Początkowo zakładamy, że liczba jest pierwsza
      boolean isPrime = true; // Czy dana liczba jest pierwsza?

      if (squareRoot * squareRoot < number) squareRoot++;

      // Sprawdzanie, czy liczba jest pierwsza
      for (int k = 0; k < list.size() 
                        && list.get(k) <= squareRoot; k++) {
        if (number % list.get(k) == 0) { // True oznacza, że liczba nie jest pierwsza
          isPrime = false; // Ustawianie isPrime na wartość false
          break; // Wyjście z pętli
        }
      }

      // Wyświetlanie liczby pierwszej i zwiększanie wartości licznika
      if (isPrime) {
        count++; // Zwiększanie wartości licznika
        list.add(number); // Dodawanie nowej liczby pierwszej do listy
        if (count % NUMBER_PER_LINE == 0) {
          // Wyświetlanie liczby i przejście do następnego wiersza
          System.out.println(number);
        }
        else
          System.out.print(number + " ");
      }

      // Sprawdzanie, czy następna liczba jest pierwsza
      number++;
    }

    System.out.println("\n" + "Ile liczb pierwszych mniejszych lub równych " +
      n + "? " + count);
  }
}
