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

namespace ConsoleApplication1
{
    public class Atkin 
    {
        private readonly List<long> primes;
        private readonly long limit;

        public Atkin(long limit)
        {
            this.limit = limit;
            primes = new List<long>();
        }



        private void FindPrimes()
        {
            var isPrime = new bool[limit + 1];
            var sqrt = Math.Sqrt(limit);
            //www.bilgisayarkavramlari.com
            for (long x = 1; x <= sqrt; x++)
                for (long y = 1; y <= sqrt; y++)
                {
                    var n = 4 * x * x + y * y;            
                    if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                        isPrime[n] ^= true;
                    n = 3 * x * x + y * y;
                    if (n <= limit && n % 12 == 7)
                        isPrime[n] ^= true;
                    n = 3 * x * x - y * y;
                    if (x > y && n <= limit && n % 12 == 11)
                        isPrime[n] ^= true;
                }

            for (long n = 5; n <= sqrt; n++)
                if (isPrime[n])
                {
                    var s = n * n;
                    for (long k = s; k <= limit; k += s)
                        isPrime[k] = false;
                }

            primes.Add(2);
            primes.Add(3);
            for (long n = 5; n <= limit; n += 2)
                if (isPrime[n])
                    primes.Add(n);
        }
        public static void Main(String[] args)
        {
            Atkin a = new Atkin(40);
            a.FindPrimes();
            
            for (int i = 0; i < a.primes.Count; i++)
            {
                Console.WriteLine(a.primes[i]);
            }
            Console.ReadKey();
            
        }
    }
    
}