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
{
class PrimeNumber
{
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
Console.WriteLine("Enter your Target?");
// Read the target number and convert to integer
int target = Int32.Parse(Console.ReadLine());
// 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,
// instead of immediately closing
Console.ReadLine();
}
}
}
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:
ReplyDelete...
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
I mean the equation 11 * x = 121 cannot become true for any x > 11.
ReplyDeleteNice Don
ReplyDeleteConsole.WriteLine("Please Enter the Target Number:");
ReplyDeleteint targetnumber = 0;
targetnumber = Convert.ToInt32(Console.ReadLine());
//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");
}
Console.ReadKey();