using System;
using System.Collections.Generic;
using System.Text;

//////////////////////////////////////////////////////////
// Name: Peter M. Maurer
// Program: Sieve of Eratosthenes
// Due: Never
// Language: C#
//////////////////////////////////////////////////////////

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] Candidates = new int[1000];
            int i;
            for (i = 0; i < 1000; i++)
            {
                // everything is potentially prime until proven otherwise
                Candidates[i] = 1;
            }
            // Neither 1 nor 0 is prime, so flag them off
            Candidates[0] = 0;
            Candidates[1] = 0;
            // start the sieve with the integer 0
            i = 0;
            while (i < 1000)
            {
                // advance to the next un-crossed out number.
                // this number must be a prime
                while (i < 1000 && Candidates[i] == 0)
                {
                    i++;
                }
                // insure against running off the end of the data structure
                if (i < 1000)
                {
                    // cross out all multiples of the prime, starting with 2*p.
                    int j;
                    for (j = 2; j * i < 1000; j++)
                    {
                        Candidates[j * i] = 0;
                    }
                    // advance to the next candidate
                    i++;
                }
            }
            // all uncrossed-out numbers are prime (and only those numbers)
            // print all primes
            for (i = 0; i < 1000; i++)
            {
                if (Candidates[i] != 0)
                {
                    Console.Write(i);
                    Console.WriteLine(" is prime");
                }
            }
        }
    }
}