//////////////////////////////////////////////////////////////////////////////
//
//  Finding prime numbers
//  (c) Johna Smith, 1996
//
//  Method description:
//   We take a number and try to divide it. If we can divide it
//   without remainder - this is not prime number.
//   We can take into account only odd numbers, because we can
//   divide all even number by 2. Also we can store all prime
//   numbers that are already found in an array and try to divide
//   all new numbers only by numbers from this array.
//   If we want to find all prime numbers less than N the size of
//   the array should be sqrt(N)/2
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

#define N   160  // so we can find all prime numbers that are less than 100000
#define M   25   // check all numbers less than 250

int Simple[N];
int k=0;
enum {yes,no} simple;

void main(void)
{
// it's easy: 2 and 3 are prime
if (M>=2) printf("2\n");                    // 2 is simple 'cause we can divide it only by itself and 1
Simple[k++]=2;
if (M>=3) printf("3\n");
Simple[k++]=3;

// but what we can say about other numbers:
for(int i=5; i<=M; i+=2)
{
   simple=yes;
   for(int j=0; j<k; j++)
   {
     if (Simple[j]*Simple[j]>i) break;     // other Simple[j] is too big for i
     if ((i%Simple[j])==0) simple=no;    // there's no remainder - not prime
   }
   if (simple==yes)
   {
     printf("%d\n",i);
     Simple[k++]=i;
   }
}
}