1 million prime number generation in less then half of a second …

This is an optimized code of prime number generation.
This question was asked in an entry test of a software house that how can you generate 1 million prime numbers in less then a second.
I wrote the code that generates the prime number and add to a list in 0.39 seconds to be specific 390.8387 milliseconds.

Important key point here to understand is that except 2 no even number is prime so that is why i have started it from 3 and increment 2 so by this why we will not be checking any even number.
public static void prime()
List l = new List(1000000);

for (uint i = 3; i < 1000000; i += 2)
bool isprime = true;
for (uint j = 3; j*j <= i; j += 2)
if (i % j == 0)
isprime = false;
if (isprime == true)

And to execute code and also calculate the running time you will need the following code.

Stopwatch stopWatch = new Stopwatch();
prime();//Prime Function
TimeSpan ts = stopWatch.Elapsed;
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
ts.Hours, ts.Minutes, ts.Seconds,
ts.Milliseconds / 10);
Console.WriteLine("RunTime " + elapsedTime);
Console.WriteLine("RunTime " + stopWatch.Elapsed.TotalMilliseconds);


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s