using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Tìm số nguyên tố sử dụng thuật toán Sàng Eratosthenes");

        int n;

        Console.WriteLine("Nhập vào số cần tìm số nguyên tố nhỏ hơn:");

        n = int.Parse(Console.ReadLine());

        bool [] a = new bool[n+1];

        //Khởi tạo mảng khởi tạo ban đầu đều là số nguyên tố

        for(int i=2; i<=n;i++)

            a[i] = true;

        //Tìm số nguyên tố

        for(int i=2; i<Math.Sqrt(n);i++)

        {

            if(a[i])

            {

                int j = (int)Math.Pow(i,2);

                while(j <=n)

                {

                    a[j] = false;

                    j += i;

                }

            }

        }

        Console.WriteLine("Các số nguyên tố là:");

        for(int i=2; i<=n;i++)

            if(a[i])

                Console.Write("{0}, ",i);       

    }

}