// Write a program that finds all prime numbers in the range [1...10 000 000].
// Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

using System;

class primeNumbers
{
    static void Main(string[] args)
    {
        int[] arr = new int[5000001];
        arr[0] = 0;
        for (int i = 1, j = 1; i < 5000001; i++, j+= 2) // Записваме в масива само нечетни числа
        {
            arr[i] = j;
        }
        Console.Write(arr[1] + " ");
        for (int i = 2; i <= 1582; i++) // Проверяваме до корен квадратен от 10 000 000 => 1582 е                     позицията на необходимото ни число (3163)
        {
            if (arr[i] != 0)            // Същевременно печатаме получените прости числа до корена                     квадратен от 10 000 000
            {
                for (int j = i + 1; j < 5000001; j++)
                {
                    if (arr[j] % arr[i] == 0)
                    {
                        arr[j] = 0;
                    }
                }
                Console.Write(arr[i] + " ");
            }
        }
        for (int i = 1582; i < 5000001; i++) // Печатаме останалите прости числа
        {
            if (arr[i] != 0)
            {
                Console.Write(arr[i] + " ");
            }
        }
    }
}