/* PrimeTopDownF2004.java
 * 
 * Program to print prime numbers, top down approach.
 *
 * Carsten Butz, Spring 2004
 */

class PrimeTopDownF2004{

  public static void main(String[] args){

    for(int i=1; i<= 100; i++)
      if(isPrime(i))
	System.out.println(i);

  }

  public static boolean isPrime(int n){

    /* Method isPrime()
     * Improved algorithm: checks first for
     * negativ numbers, 0 and 1
     * then for 2
     * then for even numbers (thus different of 2)
     * then looks for potential divisors
     */

    if( n<=1 )
      return false;

    if( n==2 )
      return true;

    if( n%2==0 )
      return false; // we already know that n is different from 2!

    boolean flag = true; // we assume that n is prime;
    double bound = Math.sqrt(n); // upper bound for potential divisors
    int d = 3; // divisor variable

    while( d<=bound && flag ){
      if( n%d==0)
	flag = false;
      d+=2;
    }

    return flag;
  }

}