Fast prime numbers between range
<p>I am trying to develop one program for develop very fast prime numbers. Prime numbers are to be generated in range (Range &lt;= 10000) and the result should be printed in under 6 seconds. This is the program i have made so far. It runs just fine on my machine 1.73 core 2 duo and produces result in under 3 seconds. But when i submit it to online program submission validator it gives time limit exceeded. I have even removed try catch block etc as i thought removing try catch may save few resources and buy me few milliseconds, but no matter whatever i do i always get time limit exceeded. This is my code :-</p>

<pre><code>using System;
using System.Collections.Generic;
using System.Linq;

namespace PrimeNumberGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
                int T = Convert.ToInt32(Console.ReadLine());
                List&lt;string&gt; listInput = new List&lt;string&gt;();

                for (int i = 0; i &lt; T; i++)
                    listInput.Add(Console.ReadLine());

                for (int i = 0; i &lt; T; i++)
                {
                    string[] str = listInput[i].Split(' ');
                    int M = Convert.ToInt32(str[0]);
                    int N = Convert.ToInt32(str[1]);

                    if ((N - M) &lt;= 100000 &amp;&amp; M &gt;= 1 &amp;&amp; M &lt;= 1000000000 &amp;&amp; N &gt;= 1 &amp;&amp; N &lt;= 1000000000)
                    {
                        int[] list = Enumerable.Range(M, (N - M + 1)).ToArray();
                        int k = 2;
                        while (true)
                        {
                            if ((k * k) &gt; N)
                                break;
                            for(int j = 0 ; j &lt; list.Count() ;j++)
                            {
                                if (list[j] != k &amp;&amp; (list[j] % k) == 0 &amp;&amp; list[j] != 1 &amp;&amp; list[j] != -1)
                                    list[j] = -1;
                            }

                            k++;
                        }

                        foreach (int item in list)
                        {
                            if (item != -1)
                                Console.WriteLine(item);
                        }

                    }
                    else
                        Console.WriteLine("Limit exceeded");
                }

        }
    }
}
</code></pre>

<p>You have to give input like this :-</p>

<p>1</p>

<p>2 30 </p>

<p>1 is no of test case and 2 and 30 mean that all primes between 2 and 30 should be produced.
You can give it 1 if you are only testing it once. I will be very grateful if you can optimise this program</p>

<p>Thanks in advance :)</p>

<p>EDIT :-</p>

<p>This is the original implmentation that i thought but obviously has overhead of list :-</p>

<pre><code>using System;
using System.Collections.Generic;
using System.Linq;

namespace PrimeNumberGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                int T = Convert.ToInt32(Console.ReadLine());
                List&lt;string&gt; listInput = new List&lt;string&gt;();

                for (int i = 0; i &lt; T; i++)
                    listInput.Add(Console.ReadLine());

                for (int i = 0; i &lt; T; i++)
                {
                    string[] str = listInput[i].Split(' ');
                    int M = Convert.ToInt32(str[0]);
                    int N = Convert.ToInt32(str[1]);

                    List&lt;int&gt; list = null;
                    if ((N - M) &lt;= 100000 &amp;&amp; M &gt;= 1 &amp;&amp; M &lt;= 1000000000 &amp;&amp; N &gt;= 1 &amp;&amp; N &lt;= 1000000000)
                    {
                        list = Enumerable.Range(M, (N - M + 1)).ToList();
                        int k = 2;
                        while (true)
                        {
                            if ((k * k) &gt; N)
                                break;
                            List&lt;int&gt; tempList = new List&lt;int&gt;();
                            foreach (int item in list)
                                if (item != k &amp;&amp; (item % k) == 0 &amp;&amp; item != 1)
                                    tempList.Add(item);
                            list = list.Except(tempList).ToList();
                            k++;
                        }

                        //list.Remove(1);
                        foreach (int item in list)
                            Console.WriteLine(item);
                        Console.WriteLine();

                    }
                    else
                        Console.WriteLine("Limit exceeded");
                }


            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            Console.ReadKey();
        }
    }
}
</code></pre>
