/*************************************************/
// primes.cpp
// R. A. Hillyard
// Last Modified:  02/16/2001
//
// program to compute all the primes up to max value
// where max value is set by the program
/*************************************************/

#include<iostream>
#include<iomanip>
#include<cmath>

using namespace std;

int main()
  {
  const int MaxNum = 500;     //define range to check
  int k = 0;                  //counter for outer loop
  int j = 0;                  //counter for inner loop
  int i = 1;                  //counter for output control

  cout << setw(5) << 2;         //print first prime (only even prime) - need iomanip for setw
  for(k=3; k<=MaxNum; k+=2)     //outer loop checks all odd numbers up to MaxNum
    {
    int lastDiv = sqrt(k);      //calculate the square root of k -> need cmath
    
    for(j=3; j<=lastDiv; j+=2)  //inner loop checks each odd division
      {
      if((k%j) == 0)            //not prime if i find a division -> exit inner loop
        break;
      }//end for j
    
    if(j > lastDiv)              //if past last possible division -> must be prime
      {
      cout << setw(5) << k;     //print each prime in a field 5 chars wide
      i++;                      //keep track of how many primes printed so far
      if((i%15)==0)             //print newline every 15 primes
        cout << endl;
      }//end if j>lastDiv
    }//end for k
  cout << endl;
  return 0;
  }//end main

/******************************Program Output*******************************
    2    3    5    7   11   13   17   19   23   29   31   37   41   43   47
   53   59   61   67   71   73   79   83   89   97  101  103  107  109  113
  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197
  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281
  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379
  383  389  397  401  409  419  421  431  433  439  443  449  457  461  463
  467  479  487  491  499
*/