Skip to main content

Find the composite numbers from 1 to n

Composite numbers are positive integers greater than 1 that have more than two positive divisors. In other words, they are numbers that can be divided evenly by at least three positive integers: 1, the number itself, and at least one other divisor. Composite numbers are distinct from prime numbers, which only have two positive divisors: 1 and the number itself.

Examples of composite numbers include 4, 6, 8, 9, 10, 12, 14, 15, and so on. Prime numbers, on the other hand, are numbers that have only two divisors, like 2, 3, 5, 7, 11, and so forth. The study of prime and composite numbers is a fundamental topic in number theory, a branch of mathematics.

Problem Statement

Given an integer n, we need to find and display all the composite numbers within the range of 1 to n.

Example

Let's consider a few examples to illustrate the problem:

  • For n = 3, there are no composite numbers within the range from 1 to 3.
  • For n = 20, the composite numbers are: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20].
  • For n = 100, the composite numbers are much more extensive: [4, 6, 8, 9, 10, ..., 100].

Idea to Solve

To solve this problem, we can use a function isPrime that checks whether a given number is prime or not. If a number is not prime, it is a composite number. The isPrime function iterates through potential divisors of the number up to its square root. If it finds any divisor other than 1 and itself, the number is not prime and is therefore composite.

We then iterate through the range from 4 to n and call the isPrime function on each number. If the function returns false, we print the number as it is a composite number.

Pseudocode

function isPrime(num):
    if num is 2, 3, or 5:
        return true
    if num is less than or equal to 1 or num is divisible by 2, 3, or 5:
        return false
    i = 11
    while i * i is less than or equal to num:
        if num is divisible by i:
            return false
        else if num is divisible by i + 2:
            return false
        i = i + 6
    return true

function compositeNo(n):
    print "Composite numbers from (1 to", n, ") is"
    result = false
    for i from 4 to n:
        if isPrime(i) is false:
            print i, "\t"
            result = true
    if result is false:
        print "None"

function main():
    compositeNo(3)
    compositeNo(20)
    compositeNo(100)

main()

Algorithm Explanation

  1. The isPrime function checks whether a given number is prime using the trial division method.
  2. The compositeNo function takes an integer n as input and prints the header for the range of numbers.
  3. It initializes a variable result to false, which will be used to check if any composite numbers were found.
  4. It iterates through the range from 4 to n and calls the isPrime function on each number.
  5. If the function returns false, indicating that the number is not prime, it prints the number and sets result to true.
  6. If no composite numbers were found (result is still false), it prints "None".

Code Solution

// C Program 
// Find the composite numbers from 1 to n
#include <stdio.h>

// Check that whether given number is prime or not
int isPrime(int num)
{
	if (num == 2 || num == 3 || num == 5)
	{
		return 1;
	}
	if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
	{
		return 0;
	}
	int i = 11;
	while ((i *i) <= num)
	{
		if (num % i == 0)
		{
			//When number is divisible of current i value
			return 0;
		}
		else if (num % (i + 2) == 0)
		{
			//When number is divisible of current i + 2 value
			return 0;
		}
		i = i + 6;
	}
	return 1;
}
// Find composite numbers from 1 to n
void compositeNo(int n)
{
	// Display the given n ( 1 to n)
	printf("\n Composite numbers from (1 to %d) is \n", n);
	int result = 0;
	// Execute loop through by n
	for (int i = 4; i <= n; ++i)
	{
		if (isPrime(i) == 0)
		{
			result = 1;
			printf("  %d", i);
		}
	}
	if (result == 0)
	{
		// When no get composite number
		printf(" None");
	}
	
}
int main(int argc, char const *argv[])
{
  
  	// 1 to 3
  	compositeNo(3);
	// 1 to 20 
	compositeNo(20);
	// 1 to 100 
	compositeNo(100);
	return 0;
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
/*
    Java Program
    Find the composite numbers from 1 to n
*/
public class CompositeNumber
{
    // Check that whether given number is prime or not
    public int isPrime(int num)
    {
        if (num == 2 || num == 3 || num == 5)
        {
            return 1;
        }
        if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
        {
            return 0;
        }
        int i = 11;
        while ((i * i) <= num)
        {
            if (num % i == 0)
            {
                //When number is divisible of current i value
                return 0;
            }
            else if (num % (i + 2) == 0)
            {
                //When number is divisible of current i + 2 value
                return 0;
            }
            i = i + 6;
        }
        return 1;
    }
    // Find composite numbers from 1 to n
    public void compositeNo(int n)
    {
        // Display the given n ( 1 to n)
        System.out.print("\n Composite numbers from (1 to " + n + ") is \n");
        boolean result = false;
        // Execute loop through by n
        for (int i = 4; i <= n; ++i)
        {
            if (isPrime(i) == 0)
            {
                result = true;
                System.out.print("  " + i );
            }
        }
        if (result == false)
        {
            // When no get composite number
            System.out.print(" None");
        }
    }
    public static void main(String[] args)
    {
        CompositeNumber task = new CompositeNumber();

        // n = 3
        task.compositeNo(3);
        // n = 20 
        task.compositeNo(20);
        // n = 100 
        task.compositeNo(100);
    }
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
// Include header file
#include <iostream>
using namespace std;

/*
    C++ Program
    Find the composite numbers from 1 to n
*/

class CompositeNumber
{
	public:
		// Check that whether given number is prime or not
		int isPrime(int num)
		{
			if (num == 2 || num == 3 || num == 5)
			{
				return 1;
			}
			if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
			{
				return 0;
			}
			int i = 11;
			while ((i *i) <= num)
			{
				if (num % i == 0)
				{
					//When number is divisible of current i value
					return 0;
				}
				else if (num % (i + 2) == 0)
				{
					//When number is divisible of current i + 2 value
					return 0;
				}
				i = i + 6;
			}
			return 1;
		}
	// Find composite numbers from 1 to n
	void compositeNo(int n)
	{
		// Display the given n ( 1 to n)
		cout << "\n Composite numbers from (1 to " << n << ") is \n";
		bool result = false;
		// Execute loop through by n
		for (int i = 4; i <= n; ++i)
		{
			if (this->isPrime(i) == 0)
			{
				result = true;
				cout << "  " << i;
			}
		}
		if (result == false)
		{
			// When no get composite number
			cout << " None";
		}
	}
};
int main()
{
	CompositeNumber task = CompositeNumber();
	// n = 3
	task.compositeNo(3);
	// n = 20
	task.compositeNo(20);
	// n = 100
	task.compositeNo(100);
	return 0;
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
// Include namespace system
using System;
/*
    C# Program
    Find the composite numbers from 1 to n
*/
public class CompositeNumber
{
	// Check that whether given number is prime or not
	public int isPrime(int num)
	{
		if (num == 2 || num == 3 || num == 5)
		{
			return 1;
		}
		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
		{
			return 0;
		}
		int i = 11;
		while ((i * i) <= num)
		{
			if (num % i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if (num % (i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			i = i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	public void compositeNo(int n)
	{
		// Display the given n ( 1 to n)
		Console.Write("\n Composite numbers from (1 to " + n + ") is \n");
		Boolean result = false;
		// Execute loop through by n
		for (int i = 4; i <= n; ++i)
		{
			if (isPrime(i) == 0)
			{
				result = true;
				Console.Write("  " + i);
			}
		}
		if (result == false)
		{
			// When no get composite number
			Console.Write(" None");
		}
	}
	public static void Main(String[] args)
	{
		CompositeNumber task = new CompositeNumber();
		// n = 3
		task.compositeNo(3);
		// n = 20
		task.compositeNo(20);
		// n = 100
		task.compositeNo(100);
	}
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
<?php
/*
    Php Program
    Find the composite numbers from 1 to n
*/
class CompositeNumber
{
	// Check that whether given number is prime or not
	public	function isPrime($num)
	{
		if ($num == 2 || $num == 3 || $num == 5)
		{
			return 1;
		}
		if ($num <= 1 || ($num % 2 == 0) || ($num % 3 == 0) || ($num % 5 == 0))
		{
			return 0;
		}
		$i = 11;
		while (($i * $i) <= $num)
		{
			if ($num % $i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if ($num % ($i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			$i = $i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	public	function compositeNo($n)
	{
		// Display the given n ( 1 to n)
		echo "\n Composite numbers from (1 to ". $n .") is \n";
		$result = false;
		// Execute loop through by n
		for ($i = 4; $i <= $n; ++$i)
		{
			if ($this->isPrime($i) == 0)
			{
				$result = true;
				echo "  ". $i;
			}
		}
		if ($result == false)
		{
			// When no get composite number
			echo " None";
		}
	}
}

function main()
{
	$task = new CompositeNumber();
	// n = 3
	$task->compositeNo(3);
	// n = 20
	$task->compositeNo(20);
	// n = 100
	$task->compositeNo(100);
}
main();

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
/*
    Node Js Program
    Find the composite numbers from 1 to n
*/
class CompositeNumber
{
	// Check that whether given number is prime or not
	isPrime(num)
	{
		if (num == 2 || num == 3 || num == 5)
		{
			return 1;
		}
		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
		{
			return 0;
		}
		var i = 11;
		while ((i * i) <= num)
		{
			if (num % i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if (num % (i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			i = i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	compositeNo(n)
	{
		// Display the given n ( 1 to n)
		process.stdout.write("\n Composite numbers from (1 to " + n + ") is \n");
		var result = false;
		// Execute loop through by n
		for (var i = 4; i <= n; ++i)
		{
			if (this.isPrime(i) == 0)
			{
				result = true;
				process.stdout.write("  " + i);
			}
		}
		if (result == false)
		{
			// When no get composite number
			process.stdout.write(" None");
		}
	}
}

function main()
{
	var task = new CompositeNumber();
	// n = 3
	task.compositeNo(3);
	// n = 20
	task.compositeNo(20);
	// n = 100
	task.compositeNo(100);
}
main();

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
#   Python 3 Program
#   Find the composite numbers from 1 to n

class CompositeNumber :
	#  Check that whether given number is prime or not
	def isPrime(self, num) :
		if (num == 2 or num == 3 or num == 5) :
			return 1
		
		if (num <= 1 or(num % 2 == 0) or(num % 3 == 0) or(num % 5 == 0)) :
			return 0
		
		i = 11
		while ((i * i) <= num) :
			if (num % i == 0) :
				# When number is divisible of current i value
				return 0
			
			elif(num % (i + 2) == 0) :
				# When number is divisible of current i + 2 value
				return 0
			
			i = i + 6
		
		return 1
	
	#  Find composite numbers from 1 to n
	def compositeNo(self, n) :
		#  Display the given n ( 1 to n)
		print("\n Composite numbers from (1 to ", n ,") is ")
		i = 4
		result = False
		#  Execute loop through by n
		while (i <= n) :
			if (self.isPrime(i) == 0) :
				result = True
				print("  ", i, end = "")
			
			i += 1
		
		if (result == False) :
			#  When no get composite number
			print(" None", end = "")
		
	

def main() :
	task = CompositeNumber()
	#  n = 3
	task.compositeNo(3)
	#  n = 20
	task.compositeNo(20)
	#  n = 100
	task.compositeNo(100)

if __name__ == "__main__": main()

Output

 Composite numbers from (1 to  3 ) is
 None
 Composite numbers from (1 to  20 ) is
   4   6   8   9   10   12   14   15   16   18   20
 Composite numbers from (1 to  100 ) is
   4   6   8   9   10   12   14   15   16   18   20   21   22   24   25   26   27   28   30   32   33   34   35   36   38   39   40   42   44   45   46   48   50   51   52   54   55   56   57   58   60   62   63   64   65   66   68   69   70   72   74   75   76   78   80   81   82   84   85   86   87   88   90   92   93   94   95   96   98   99   100
#  Ruby Program
#  Find the composite numbers from 1 to n

class CompositeNumber 
	#  Check that whether given number is prime or not
	def isPrime(num) 
		if (num == 2 || num == 3 || num == 5) 
			return 1
		end

		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0)) 
			return 0
		end

		i = 11
		while ((i * i) <= num) 
			if (num % i == 0) 
				# When number is divisible of current i value
				return 0
			elsif(num % (i + 2) == 0) 
				# When number is divisible of current i + 2 value
				return 0
			end

			i = i + 6
		end

		return 1
	end

	#  Find composite numbers from 1 to n
	def compositeNo(n) 
		#  Display the given n ( 1 to n)
		print("\n Composite numbers from (1 to ", n ,") is \n")
		i = 4
		result = false
		#  Execute loop through by n
		while (i <= n) 
			if (self.isPrime(i) == 0) 
				result = true
				print("  ", i)
			end

			i += 1
		end

		if (result == false) 
			#  When no get composite number
			print(" None")
		end

	end

end

def main() 
	task = CompositeNumber.new()
	#  n = 3
	task.compositeNo(3)
	#  n = 20
	task.compositeNo(20)
	#  n = 100
	task.compositeNo(100)
end

main()

Output

 Composite numbers from (1 to 3) is 
 None
 Composite numbers from (1 to 20) is 
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is 
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
/*
    Scala Program
    Find the composite numbers from 1 to n
*/
class CompositeNumber
{
	// Check that whether given number is prime or not
	def isPrime(num: Int): Int = {
		if (num == 2 || num == 3 || num == 5)
		{
			return 1;
		}
		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
		{
			return 0;
		}
		var i: Int = 11;
		while ((i * i) <= num)
		{
			if (num % i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if (num % (i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			i = i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	def compositeNo(n: Int): Unit = {
		// Display the given n ( 1 to n)
		print("\n Composite numbers from (1 to " + n + ") is \n");
		var i: Int = 4;
		var result: Boolean = false;
		// Execute loop through by n
		while (i <= n)
		{
			if (this.isPrime(i) == 0)
			{
				result = true;
				print("  " + i);
			}
			i += 1;
		}
		if (result == false)
		{
			// When no get composite number
			print(" None");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: CompositeNumber = new CompositeNumber();
		// n = 3
		task.compositeNo(3);
		// n = 20
		task.compositeNo(20);
		// n = 100
		task.compositeNo(100);
	}
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100
/*
    Swift 4 Program
    Find the composite numbers from 1 to n
*/
class CompositeNumber
{
	// Check that whether given number is prime or not
	func isPrime(_ num: Int)->Int
	{
		if (num == 2 || num == 3 || num == 5)
		{
			return 1;
		}
		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
		{
			return 0;
		}
		var i: Int = 11;
		while ((i * i) <= num)
		{
			if (num % i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if (num % (i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			i = i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	func compositeNo(_ n: Int)
	{
		// Display the given n ( 1 to n)
		print("\n Composite numbers from (1 to ", n ,") is ");
		var i: Int = 4;
		var result: Bool = false;
		// Execute loop through by n
		while (i <= n)
		{
			if (self.isPrime(i) == 0)
			{
				result = true;
				print("  ", i, terminator: "");
			}
			i += 1;
		}
		if (result == false)
		{
			// When no get composite number
			print(" None", terminator: "");
		}
	}
}
func main()
{
	let task: CompositeNumber = CompositeNumber();
	// n = 3
	task.compositeNo(3);
	// n = 20
	task.compositeNo(20);
	// n = 100
	task.compositeNo(100);
}
main();

Output

 Composite numbers from (1 to  3 ) is
 None
 Composite numbers from (1 to  20 ) is
   4   6   8   9   10   12   14   15   16   18   20
 Composite numbers from (1 to  100 ) is
   4   6   8   9   10   12   14   15   16   18   20   21   22   24   25   26   27   28   30   32   33   34   35   36   38   39   40   42   44   45   46   48   50   51   52   54   55   56   57   58   60   62   63   64   65   66   68   69   70   72   74   75   76   78   80   81   82   84   85   86   87   88   90   92   93   94   95   96   98   99   100
/*
    Kotlin Program
    Find the composite numbers from 1 to n
*/
class CompositeNumber
{
	// Check that whether given number is prime or not
	fun isPrime(num: Int): Int
	{
		if (num == 2 || num == 3 || num == 5)
		{
			return 1;
		}
		if (num <= 1 || (num % 2 == 0) || (num % 3 == 0) || (num % 5 == 0))
		{
			return 0;
		}
		var i: Int = 11;
		while ((i * i) <= num)
		{
			if (num % i == 0)
			{
				//When number is divisible of current i value
				return 0;
			}
			else if (num % (i + 2) == 0)
			{
				//When number is divisible of current i + 2 value
				return 0;
			}
			i = i + 6;
		}
		return 1;
	}
	// Find composite numbers from 1 to n
	fun compositeNo(n: Int): Unit
	{
		// Display the given n ( 1 to n)
		print("\n Composite numbers from (1 to " + n + ") is \n");
		var i: Int = 4;
		var result: Boolean = false;
		// Execute loop through by n
		while (i <= n)
		{
			if (this.isPrime(i) == 0)
			{
				result = true;
				print("  " + i);
			}
			i += 1;
		}
		if (result == false)
		{
			// When no get composite number
			print(" None");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: CompositeNumber = CompositeNumber();
	// n = 3
	task.compositeNo(3);
	// n = 20
	task.compositeNo(20);
	// n = 100
	task.compositeNo(100);
}

Output

 Composite numbers from (1 to 3) is
 None
 Composite numbers from (1 to 20) is
  4  6  8  9  10  12  14  15  16  18  20
 Composite numbers from (1 to 100) is
  4  6  8  9  10  12  14  15  16  18  20  21  22  24  25  26  27  28  30  32  33  34  35  36  38  39  40  42  44  45  46  48  50  51  52  54  55  56  57  58  60  62  63  64  65  66  68  69  70  72  74  75  76  78  80  81  82  84  85  86  87  88  90  92  93  94  95  96  98  99  100

Time Complexity

The time complexity of the isPrime function is approximately O(√n), as it iterates through potential divisors up to the square root of the given number n.

The compositeNo function iterates through the range from 4 to n and calls the isPrime function for each number. Therefore, the time complexity of the compositeNo function is O(n√n).

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment