using System; using System.Collections.Generic; using System.Linq; public class Program{ public static void Main(){ var n = long.Parse(Console.ReadLine()); var N = (long)Math.Truncate(Math.Sqrt(n)); var k = Prime(N); var a = new List(); for(var i=0;i Prime(long n) { var isPrime = new bool[n+1]; var k = new List(); for (int i = 2; i <= n; i++) { isPrime[i] = true; } for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } for (int i = 2; i <= n; i++) { if (isPrime[i]) { k.Add(i); } } return k; } }