// ShowSieve.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* Utilizes NumberTable.java to illustrate how a 
   Prime sieve changes over time.

   The number table is a grid of boxes containing the
   integers from 1 to n. The table used here always 
   has 10 columns.

   As the sieve progresses, numbers which have been found
   to be not prime are marked as 'invalid' in the table.

   To make the sieving understandable, execution pauses 
   momentarily after each prime multiple has been invalidated.
   Also, the program waits for the user to press <enter>
   after all the multiple of a prime have been invalidated.

  https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

   Usage:
     > compile ShowSieve.java
     > run ShowSieve <n>
   e.g.
     > run ShowSieve 100
     > run ShowSieve 200
     > run ShowSieve 300
*/

public class ShowSieve
{
  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: run ShowSieve <n>");
      return;
    }
    int n = Math.abs(Nut.parseInt(args[0]));

    int numRows = (int)Math.ceil(((double)n)/10);
    NumberTable nt = new NumberTable(numRows, 10);
            // the table always has 10 columns
    nt.setValid(1, false);   // mark box '1' as 'invalid'

    Nut.pause(1000);
    // Sieve of Eratosthenes
    int max = (int) Math.sqrt(n) + 1;
    System.out.println("Max sieve: " + max);

    for (int p = 2; p < max; p++) {
      if (Nut.isPrime(p)) {
        System.out.println(p + " prime; invalidate all still-valid multiples... ");
        for (int i = p*p; i <= n; i += p) {   // remove p multiples
          if (nt.isValid(i)) {
            nt.setValid(i, false);
            System.out.print(" " + i);
            if (p != 2)
              Nut.pause(300);  // wait a bit after the removal of each
                               // p multiple, except when dealing with p == 2
          }
        }
        System.out.println();
        Nut.waitEnter();  // wait for the user after p's multiple 
                          // have been invalidated
      }
    }
    System.out.println("Finished sieving");
  } /* main */


}  // end of ShowSieve class