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
- The
isPrime
function checks whether a given number is prime using the trial division method. - The
compositeNo
function takes an integern
as input and prints the header for the range of numbers. - It initializes a variable
result
tofalse
, which will be used to check if any composite numbers were found. - It iterates through the range from 4 to
n
and calls theisPrime
function on each number. - If the function returns
false
, indicating that the number is not prime, it prints the number and setsresult
totrue
. - If no composite numbers were found (
result
is stillfalse
), 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).
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