C# Method to Check if a Number is Composite

In a previous post, we developed a C# method to check if an integer is a prime number or not. Today, we are going to develop a C# method to check if an integer is composite number or not. First, let's learn what is a composite number.

What is a Composite Number?

Any integer that is prime is then considered as composite number because it can be divided by more than two numbers. Composite numbers are integers that have more than two factors. To summarize, an integer that can be divided by itself and by a number that is greater than 1, is called a composite number.

Always remember the following two rules:

  • Any integer that is greater than 1 is either a composite number or a prime number.
  • 1 is an integer that is neither prime nor composite.

So how can we check if a given integer is a composite number or not?

We can use the prime method we built in the other post, then change the return statements by switching the return value from true to false and vice versa. As well, we can use the optimized school method to check if the integer is composite number or not. In the School Method algorithm, we iterate through all the numbers from 2 to n−1 (the number to be checked is n). In the optimized school method:

Instead of iterating till n-1, we will first check the divisibility of n by 2 and 3, then check its divisibility by numbers of the form 6i−1 and 6i+1 starting at i=1. We do so because any integer greater than 4 can be expressed in the form of 6i−1, 6i, 6i+1, 6i+2, 6i+3, and 6i+4 (for i>0), but integers of the form 6i, 6i+2, 6i+3, and 6i+4 will be divisible by 2 or 3.

Let's have a look at the implementation in the section below.

using System;

class Program
{
    public static void Main()
    {
        int n = 9;
        Console.WriteLine(n + " is a composite integer: " + IsComposite(n));

        n = 23;
        Console.WriteLine(n + " is a composite integer: " + IsComposite(n));
    }
    /// <summary>
    /// A optimized C# method to check if a number is composite.
    /// </summary>
    /// <param name="n">It represents the integer we are checking</param>
    /// <returns>Returns true if composite number and false if it is not</returns>
    public static bool IsComposite(int n)
    {
        // simple case
        if (n <= 3) return false;

        // This is checked so that we can skip middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0) return true;

        // Checking through numbers of the form 6i-1 and 6i+1 (i>0)
        for (int i = 5; i * i <= n; i = i + 6)

            if (n % i == 0 || n % (i + 2) == 0)
                return true;

        return false;
    }
}

Here is the output:

9 is composite integer: True
23 is composite integer: False

In the above method, we are checking whether the given number is a composite number or not, to do so, we are first checking its divisibility by 2 and 3, then checking its divisibility by numbers of the form 6i−1 and 6i+1. If the given number is divisible by any number then it is composite number, else it is not.

Do you have better solution? Please share it with us in the comments.

Post a Comment

Previous Post Next Post