title: Using LINQ to generate prime numbers
body: <p>Following is an interview question:</p>
  
  <p>The following one-liner generates and displays the list of first 500 prime numbers. How would you optimize it using parallel LINQ while still keeping it a SINGLE C# STATEMENT:</p>
  
  <pre><code>MessageBox.Show(string.Join(",", 
      Enumerable.Range(2, (int)(500 * (Math.Log(500) + Math.Log(System.Math.Log(500)) - 0.5)))
                  .Where(x =&gt; Enumerable.Range(2, x - 2)
                                        .All(y =&gt; x % y != 0))
                  .TakeWhile((n, index) =&gt; index &lt; 500)));
  </code></pre>
  
  <p>I tried introducing <code>AsParallel()</code> as well as <code>ParallelEnumerable</code> into the query, but did not see any tangible benefits on multi-core machines. The query still uses one CPU core heavily while other cores enjoy leisure time. Can someone suggest an improvement that would distribute the load equally on all cores and thus reduce execution time?</p>
  
  <p><strong>For the enthusiast</strong>: The following formula returns an upper bound which is guaranteed to be greater than N prime numbers, i.e. if you check up to this number, you'll sure find N primes smaller than it:</p>
  
  <pre><code>UpperBound = N * (Log(N) + Log(Log(N)) - 0.5) //Log is natural log
  </code></pre>