1  import java.util.Scanner;
  2  
  3  public class EfficientPrimeNumbers {
  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      // A list to hold prime numbers
 10      java.util.List<Integer> list = 
 11        new java.util.ArrayList<>(); 
 12  
 13      final int NUMBER_PER_LINE = 10; // Display 10 per line
 14      int count = 0; // Count the number of prime numbers
 15      int number = 2; // A number to be tested for primeness
 16      int squareRoot = 1; // Check whether number <= squareRoot
 17  
 18      System.out.println("The prime numbers are \n");
 19  
 20      // Repeatedly find prime numbers
 21      while (number <= n) {
 22        // Assume the number is prime
 23        boolean isPrime = true; // Is the current number prime?
 24  
 25        if (squareRoot * squareRoot < number) squareRoot++;
 26  
 27        // Test whether number is prime
 28        for (int k = 0; k < list.size() 
 29                          && list.get(k) <= squareRoot; k++) {
 30          if (number % list.get(k) == 0) { // If true, not prime
 31            isPrime = false; // Set isPrime to false          
 32            break; // Exit the for loop
 33          }
 34        }
 35  
 36        // Print the prime number and increase the count
 37        if (isPrime) {
 38          count++; // Increase the count
 39          list.add(number); // Add a new prime to the list
 40          if (count % NUMBER_PER_LINE == 0) {
 41            // Print the number and advance to the new line
 42            System.out.println(number);
 43          }
 44          else
 45            System.out.print(number + " ");
 46        }
 47  
 48        // Check if the next number is prime
 49        number++;
 50      }
 51  
 52      System.out.println("\n" + count + 
 53        " prime(s) less than or equal to " + n);
 54    }
 55  }