AOJ 0202 solution by C#

AOJ0202.cs

using System;

namespace AOJ
{
    class AOJ0202
    {
        static void Main(string[] args)
        {
            var ps = Prims(1000000);

            for (;;)
            {
                var line = Console.ReadLine ().Split ();
                var n = int.Parse(line[0]);
                var m = int.Parse(line[1]);
                if (n == 0 && m == 0) break;

                var xs = new int[n];
                for (var i = 0; i < n; i++)
                {
                    xs[i] = int.Parse(Console.ReadLine());
                }

                var ans = 0;
                var dp = new bool[m + 1];
                dp[0] = true;
                for (var i = 0; i < n; i++)
                {
                    for (var j = xs[i]; j <= m; j++)
                    {
                        if (dp[j - xs[i]])
                        {
                            dp[j] = true;
                            if (ps[j])
                            {
                                ans = Math.Max(ans, j);
                            }
                        }
                    }
                }

                Console.WriteLine(ans != 0 ? ans.ToString() : "NA");
            }
        }

        static bool[] Prims(int n)
        {
            bool[] prims = new bool[n + 1];

            for (var i = 2; i <= n; i++) prims[i] = true;

            for (var i = 2; i <= n; i++)
            {
                if (prims[i])
                {
                    for (var j = i + i; j <= n; j += i) prims[j] = false;
                }
            }

            return prims;
        }
    }
}