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

namespace Euler
{
    //Brutal and dumb prime searcher.
    // Small memory footprint though, so if you've some time...
    static class Primer
    {
        private static List<long> _staPrimes;
        private static long _inc;
        private static long _i;
        static Primer()
        {
            
            _staPrimes = new List<long>();
            _i = 5;
        }

        public static List<long> Primes
        {
            get { return _staPrimes; }
            set { _staPrimes = value; }
        }

        public static void FindPrimesUntil(long lUntil)
        {  
            while (_i < lUntil)
            {
                Next();
            }
        }

        //Hint #0: start with 3 then consider only odd numbers (remove multiples of 2)
        //Hint #1: start with 5 then increments by 2 then 4 (remove multiples of 2 and 3)
        private static bool Next()
        {
            if (_staPrimes.Count == 0)
            {
                _staPrimes.Add(2);
                return true;
            }

            if (_staPrimes.Count == 1)
            {
                _staPrimes.Add(3);
                return true;
            }

            bool bSuc = isPrime(_i);
            if (_inc == 2) _inc = 4; else _inc = 2;
            _i += _inc;
            return bSuc;
        }

        public static long NextPrime()
        {
            bool bSuc = false;

            while (!bSuc) bSuc = Next();
            return _i;
        }

        private static bool isPrime(long i)
        {
            //Hint #2: Compare only with primes up to the sqrt of the candidate
            for (int j = 0; ((j < _staPrimes.Count) && (_staPrimes[j] * _staPrimes[j] <= i)); ++j)
            {
                if (i % _staPrimes[j] == 0)
                    return false;
            }
            _staPrimes.Add(i);
            return true;
        }
    }
}