MVC ASP.NET C# SQL Server WCF Written Test HR Round Subscribe C# Videos C# Programs Buy DVD

### C# program to print prime numbers

A prime number is not divisible by any other number apart from 1 and itself. So, we use this logic in this program to determine if a number is prime.

using System;

namespace SamplePrograms
{
{
public static void Main()
{
// Declare a boolean variable to determine is if a number is prime
bool isNumberComposite = false;
int j;

// Prompt the user to enter their target number

// Read the target number and convert to integer

// 1 is neither prime nor composite. So start at 2
for (int i = 2; i <= target; i++)
{
for (j = 2; j < i; j++)
{
// A number is not prime if it is divisible by any other number,
// other than 1 and itself.

if (i % j == 0)
{
isNumberComposite = true;
// We can break out of the inner for loop as we know the number
// is not prime

break;
}
}
// Print the number if it is not composite
if (!isNumberComposite)
Console.Write("{0} ", j);
else
isNumberComposite = false;
}

// This line is to make the program wait for user input,

}
}
}

1. This program could find the prime numbers much faster: Instead of incrementing the j variable up to i, it is enough to test until the square root of i:

...
int maxcheck = (int) Math.Sqrt(i);
for (j = 2; j <= maxcheck; j++)
...

With this change, i would be the prime candidate for output (instead if j):
...
if (!isNumberComposite)
Console.Write("{0} ", i);
...

The performance improvement is really significant, especially for large numbers.

Mathematically it is obvious: If an integer divisor is greater than the square root, its counterpart must be smaller and therefore has already been tested.

Example: if i = 121, then maxcheck = 11, because the equation 12 * x = 121 cannot become true for any x >= 11. So we are definitely done after checking all possible divisors up to max. 11 in this case.

Don P

2. I mean the equation 11 * x = 121 cannot become true for any x > 11.

3. 4. int targetnumber = 0;
//To get the Prime Number.
int flag = 0;
for (int i = 2; i <= targetnumber / 2; i++)
{
if (targetnumber % i== 0)
{
flag = 1;
break;
}
}
if (flag == 0)
{
Console.WriteLine(targetnumber + " is a prime number");
}
else {
Console.WriteLine(targetnumber + " is not a prime number");
}