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);

l.add(1);
l.add(2);
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;
break;
}
}
if (isprime == true)
{
l.Add(i);
//Console.WriteLine(i);
}
}
}

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

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
prime();//Prime Function
stopWatch.Stop();
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);

Advertisements

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