# 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)
{

// n = 3
// n = 20
// n = 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()
{
// n = 3
// n = 20
// n = 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)
{
// n = 3
// n = 20
// n = 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()
{
// n = 3
// n = 20
// n = 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()
{
// n = 3
// n = 20
// n = 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() :
#  n = 3
#  n = 20
#  n = 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()
#  n = 3
#  n = 20
#  n = 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
// n = 20
// n = 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()
{
// n = 3
// n = 20
// n = 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
{
// n = 3
// n = 20
// n = 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).

## 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.