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
{
    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();
        }
    }
}

4 comments:

  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

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

    ReplyDelete
  3. Console.WriteLine("Please Enter the Target Number:");
    int 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();

    ReplyDelete