Выведет все простые числа в диапазоне от 1 000 000 до 20 000 000.

                        
public class Atkin

    {

        internal readonly int _limit;

        public bool[] IsPrimes;

 

        public Atkin() { return; }

        public Atkin(int limit)

        {

            _limit = limit;

            FindPrimes();

        }

 

        public void FindPrimes()

        {

            IsPrimes = new bool[_limit + 1];

            double sqrt = Math.Sqrt(_limit);

            if (sqrt < 29301)

            {

                for (int x = 1; x <= sqrt; x++)

                    for (int y = 1; y <= sqrt; y++)

                    {

                        int x2 = x * x;

                        int y2 = y * y;

                        int n = 4 * x2 + y2;

                        if (n <= _limit && (n % 12 == 1 || n % 12 == 5))

                            IsPrimes[n] ^= true;

 

                        n -= x2;

                        if (n <= _limit && n % 12 == 7)

                            IsPrimes[n] ^= true;

 

                        n -= 2 * y2;

                        if (x > y && n <= _limit && n % 12 == 11)

                            IsPrimes[n] ^= true;

                    }

 

                for (int n = 5; n <= sqrt; n += 2)

                    if (IsPrimes[n])

                    {

                        int s = n * n;

                        for (int k = s; k <= _limit; k += s)

                            IsPrimes[k] = false;

                    }

            }

            else

            {

                var limit = (ulong)_limit;

                for (ulong x = 1; x <= sqrt; x++)

                    for (ulong y = 1; y <= sqrt; y++)

                    {

                        ulong x2 = x * x;

                        ulong y2 = y * y;

                        ulong n = 4 * x2 + y2;

                        if (n <= limit && (n % 12 == 1 || n % 12 == 5))

                            IsPrimes[n] ^= true;

 

                        n -= x2;

                        if (n <= limit && n % 12 == 7)

                            IsPrimes[n] ^= true;

 

                        n -= 2 * y2;

                        if (x > y && n <= limit && n % 12 == 11)

                            IsPrimes[n] ^= true;

                    }

 

                for (ulong n = 5; n <= sqrt; n += 2)

                    if (IsPrimes[n])

                    {

                        ulong s = n * n;

                        for (ulong k = s; k <= limit; k += s)

                            IsPrimes[k] = false;

                    }

            }

            IsPrimes[2] = true;

            IsPrimes[3] = true;

        }

    }

Подпись:  

Использование:

Atkin a = new Atkin(2000000);

 

int i = 1000000

while (i < 2000000)

{

    if (a.IsPrimes[i]) Console.WriteLine(i);

}