Check if a number is semiprime or not
In this article, we will discuss how to determine whether a given number is a semiprime or not. A semiprime is a natural number that is the product of exactly two prime numbers. For example, 6 is a semiprime because it can be expressed as 2 * 3, where 2 and 3 are both prime numbers.
Problem Statement
Given a positive integer 'number,' we need to check whether it is a semiprime or not. If it is a semiprime, we need to find and display the two prime numbers whose product results in the given number.
Explanation with Suitable Example
Let's take the number 77 as an example to understand the process. We need to check if 77 is a semiprime and find its prime factors.
- First, we check if 77 is a semiprime by finding its prime factors.
- Start iterating through numbers from 2 to 77/2, which is up to 38 in this case.
- For each number, we check if it is a prime number using the 'is_prime' function.
- If the number is both prime and divides 77 evenly (77 % i == 0), then we have found one of the prime factors.
- We store the first prime factor in the variable 'first.'
- As we continue the iteration, we find the second prime factor and store it in the variable 'second.'
- If we find both 'first' and 'second' prime factors, we output that the number is a semiprime and display the two factors.
Standard Pseudocode
function is_prime(n):
if n <= 1:
return false
if n == 2 or n == 3 or n == 5:
return true
for i from 2 to n/2:
if n % i == 0:
return false
return true
function is_semiprime(number):
first = 0
second = 0
for i from 2 to number/2:
if is_prime(i) and number % i == 0:
if first == 0:
first = i
else:
second = i
break
if first != 0 and second != 0:
print number, "is a semiprime number of (", first, "X", second, ")"
else:
print number, "is not a semiprime number"
main():
is_semiprime(6)
is_semiprime(77)
is_semiprime(31)
is_semiprime(51)
Algorithm Explanation
- Define the 'is_prime' function to check whether a given number is prime or not.
- Initialize 'first' and 'second' variables to store the two prime factors of the number.
- Iterate through numbers from 2 to number/2.
- For each number, check if it is a prime number using the 'is_prime' function.
- If it is both prime and divides 'number' evenly, store it in 'first' if 'first' is empty, otherwise store it in 'second' and break out of the loop.
- After the loop, if both 'first' and 'second' are non-zero, print that the number is a semiprime with its factors; otherwise, print that the number is not a semiprime.
Code Solution
Here given code implementation process.
//C Program
//Check if a number is semiprime or not
#include <stdio.h>
//Find the given number is prime or not
int is_prime(int n) {
if (n <= 1) {
return 0;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return 1;
}
for (int i = n / 2; i > 1; --i) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
void is_semiprime(int number) {
int first = 0, second = 0;
for (int i = 2; i <= number / 2; ++i) {
if (is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
}
if (first != 0 && second != 0) {
//combination of two prime is a semiprime
printf("%d Is an semiprime number of (%d X %d)\n", number, first, second);
} else {
printf("%d Is not a semiprime number\n", number);
}
}
int main() {
//Test Case
is_semiprime(6); // 3 * 2
is_semiprime(77); //7 * 11
is_semiprime(31);
is_semiprime(51); //3 * 17
return 0;
}
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
/*
C++ Program
Check if a number is semiprime or not
*/
#include<iostream>
using namespace std;
class MyNumber {
public:
//Find the given number is prime or not
bool is_prime(int n) {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
for (int i = n / 2; i > 1; --i) {
if (n % i == 0) {
return false;
}
}
return true;
}
void is_semiprime(int number) {
int first = 0, second = 0;
for (int i = 2; i <= number / 2; ++i) {
if (this->is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
}
if (first != 0 && second != 0) {
//combination of two prime is a semiprime
cout << number << " Is an semiprime number of (" << first << " X " << second << ")\n";
} else {
cout << number << " Is not a semiprime number\n";
}
}
//3 *17
};
int main() {
MyNumber obj ;
//Test Case
obj.is_semiprime(6);
// 3 *2
obj.is_semiprime(77);
//7 *11
obj.is_semiprime(31);
obj.is_semiprime(51);
return 0;
}
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
/*
Java Program
Check if a number is semiprime or not
*/
public class MyNumber {
//Find the given number is prime or not
public boolean is_prime(int n) {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
for (int i = n / 2; i > 1; --i) {
if (n % i == 0) {
return false;
}
}
return true;
}
public void is_semiprime(int number) {
int first = 0, second = 0;
for (int i = 2; i <= number / 2; ++i) {
if (is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
}
if (first != 0 && second != 0) {
//combination of two prime is a semiprime
System.out.print(number+" Is an semiprime number of ("+first+" X "+second+")\n");
} else {
System.out.print(number+" Is not a semiprime number\n");
}
}
public static void main(String[] args) {
MyNumber obj = new MyNumber();
//Test Case
obj.is_semiprime(6); // 3 * 2
obj.is_semiprime(77); //7 * 11
obj.is_semiprime(31);
obj.is_semiprime(51); //3 * 17
}
}
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
/*
C# Program
Check if a number is semiprime or not
*/
using System;
public class MyNumber {
//Find the given number is prime or not
public Boolean is_prime(int n) {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
for (int i = n / 2; i > 1; --i) {
if (n % i == 0) {
return false;
}
}
return true;
}
public void is_semiprime(int number) {
int first = 0, second = 0;
for (int i = 2; i <= number / 2; ++i) {
if (is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
}
if (first != 0 && second != 0) {
//combination of two prime is a semiprime
Console.Write(number + " Is an semiprime number of (" + first + " X " + second + ")\n");
} else {
Console.Write(number + " Is not a semiprime number\n");
}
}
public static void Main(String[] args) {
MyNumber obj = new MyNumber();
//Test Case
obj.is_semiprime(6); // 3 * 2
obj.is_semiprime(77); //7 * 11
obj.is_semiprime(31);
obj.is_semiprime(51); //3 * 17
}
}
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
# Python 3 Program
# Check if a number is semiprime or not
class MyNumber :
#Find the given number is prime or not
def is_prime(self, n) :
if (n <= 1) :
return False
#Base case
if (n == 2 or n == 3 or n == 5) :
return True
i = n / 2
while (i > 1) :
if (n % i == 0) :
return False
i -= 1
return True
def is_semiprime(self, number) :
first = 0
second = 0
i = 2
while (i <= number / 2) :
if (self.is_prime(i) and number % i == 0) :
if (first == 0) :
#When get first semiprime
first = i
else :
#When get second semiprime
second = i
break
i += 1
if (first != 0 and second != 0) :
print(number ," Is an semiprime number of (", first ," X ", second ,")")
else :
print(number ," Is not a semiprime number")
def main() :
obj = MyNumber()
obj.is_semiprime(6)
#3 *17
obj.is_semiprime(77)
obj.is_semiprime(31)
obj.is_semiprime(51)
if __name__ == "__main__":
main()
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
# Ruby Program
# Check if a number is semiprime or not
class MyNumber
#Find the given number is prime or not
def is_prime(n)
if (n <= 1)
return false
end
#Base case
if (n == 2 or n == 3 or n == 5)
return true
end
i = n / 2
while (i > 1)
if (n % i == 0)
return false
end
i -= 1
end
return true
end
def is_semiprime(number)
first = 0
second = 0
i = 2
while (i <= number / 2)
if (self.is_prime(i) and number % i == 0)
if (first == 0)
#When get first semiprime
first = i
else
#When get second semiprime
second = i
break
end
end
i += 1
end
if (first != 0 and second != 0)
print(number ," Is an semiprime number of (", first ," X ", second ,")\n")
else
print(number ," Is not a semiprime number\n")
end
end
end
def main()
obj = MyNumber.new()
obj.is_semiprime(6) #3 *17
obj.is_semiprime(77)
obj.is_semiprime(31)
obj.is_semiprime(51)
end
main()
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
/*
Scala Program
Check if a number is semiprime or not
*/
import scala.util.control.Breaks._
class MyNumber {
//Find the given number is prime or not
def is_prime(n: Int): Boolean = {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
var i: Int = n / 2;
while (i > 1) {
if (n % i == 0) {
return false;
}
i -= 1;
}
return true;
}
def is_semiprime(number: Int): Unit = {
var first: Int = 0;
var second: Int = 0;
var i: Int = 2;
breakable {
while (i <= number / 2) {
if (this.is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
i += 1;
}
}
if (first != 0 && second != 0) {
print(s"$number Is an semiprime number of ($first X $second )\n");
} else {
print(s"$number Is not a semiprime number\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyNumber = new MyNumber();
obj.is_semiprime(6);//3 *17
obj.is_semiprime(77);
obj.is_semiprime(31);
obj.is_semiprime(51);
}
}
Output
6 Is an semiprime number of (2 X 3 )
77 Is an semiprime number of (7 X 11 )
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17 )
/*
Swift 4 Program
Check if a number is semiprime or not
*/
class MyNumber {
//Find the given number is prime or not
func is_prime(_ n: Int) -> Bool {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
var i: Int = n / 2;
while (i > 1) {
if (n % i == 0) {
return false;
}
i -= 1;
}
return true;
}
func is_semiprime(_ number: Int) {
var first: Int = 0;
var second: Int = 0;
var i: Int = 2;
while (i <= number / 2) {
if (self.is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
i += 1;
}
if (first != 0 && second != 0) {
print(number ," Is an semiprime number of (", first ," X ", second ,")");
} else {
print(number ," Is not a semiprime number");
}
}
}
func main() {
let obj: MyNumber = MyNumber();
obj.is_semiprime(6);//3 *17
obj.is_semiprime(77);
obj.is_semiprime(31);
obj.is_semiprime(51);
}
main();
Output
6 Is an semiprime number of ( 2 X 3 )
77 Is an semiprime number of ( 7 X 11 )
31 Is not a semiprime number
51 Is an semiprime number of ( 3 X 17 )
<?php
/*
Php Program
Check if a number is semiprime or not
*/
class MyNumber {
//Find the given number is prime or not
public function is_prime($n) {
if ($n <= 1) {
return false;
}
//Base case
if ($n == 2 || $n == 3 || $n == 5) {
return true;
}
for ($i = intval($n / 2); $i > 1; --$i) {
if ($n % $i == 0) {
return false;
}
}
return true;
}
public function is_semiprime($number) {
$first = 0;
$second = 0;
for ($i = 2; $i <= intval($number / 2); ++$i) {
if ($this->is_prime($i) && $number % $i == 0) {
if ($first == 0) {
//When get first semiprime
$first = $i;
} else {
//When get second semiprime
$second = $i;
break;
}
}
}
if ($first != 0 && $second != 0) {
//combination of two prime is a semiprime
echo($number ." Is an semiprime number of (". $first ." X ". $second .")\n");
} else {
echo($number ." Is not a semiprime number\n");
}
}
//3 *17
};
function main() {
$obj = new MyNumber();
//Test Case
$obj->is_semiprime(6);
// 3 *2
$obj->is_semiprime(77);
//7 *11
$obj->is_semiprime(31);
$obj->is_semiprime(51);
}
main();
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
/*
Node Js Program
Check if a number is semiprime or not
*/
class MyNumber {
//Find the given number is prime or not
is_prime(n) {
if (n <= 1) {
return false;
}
//Base case
if (n == 2 || n == 3 || n == 5) {
return true;
}
for (var i = parseInt(n / 2); i > 1; --i) {
if (n % i == 0) {
return false;
}
}
return true;
}
is_semiprime(number) {
var first = 0;
var second = 0;
for (var i = 2; i <= parseInt(number / 2); ++i) {
if (this.is_prime(i) && number % i == 0) {
if (first == 0) {
//When get first semiprime
first = i;
} else {
//When get second semiprime
second = i;
break;
}
}
}
if (first != 0 && second != 0) {
//combination of two prime is a semiprime
process.stdout.write(number + " Is an semiprime number of (" + first + " X " + second + ")\n");
} else {
process.stdout.write(number + " Is not a semiprime number\n");
}
}
//3 *17
}
function main(args) {
var obj = new MyNumber();
//Test Case
obj.is_semiprime(6);// 3 *2
obj.is_semiprime(77);//7 *11
obj.is_semiprime(31);
obj.is_semiprime(51)
}
main();
Output
6 Is an semiprime number of (2 X 3)
77 Is an semiprime number of (7 X 11)
31 Is not a semiprime number
51 Is an semiprime number of (3 X 17)
Resultant Output Explanation
Let's analyze the output of the provided test cases:
-
is_semiprime(6): Output - "6 Is a semiprime number of (2 X 3)" Explanation: 6 can be expressed as a product of two prime numbers: 2 * 3.
-
is_semiprime(77): Output - "77 Is a semiprime number of (7 X 11)" Explanation: 77 can be expressed as a product of two prime numbers: 7 * 11.
-
is_semiprime(31): Output - "31 Is not a semiprime number" Explanation: 31 is a prime number and cannot be expressed as a product of two distinct prime numbers.
-
is_semiprime(51): Output - "51 Is a semiprime number of (3 X 17)" Explanation: 51 can be expressed as a product of two prime numbers: 3 * 17.
Time Complexity of the Code
Let's analyze the time complexity of the code:
- The 'is_prime' function has a time complexity of O(sqrt(n)) as it iterates up to n/2 to check for divisibility.
- The 'is_semiprime' function has a loop that iterates up to number/2, and within it, it calls 'is_prime,' so the overall time complexity of this function is O(number * sqrt(number)).
In conclusion, the provided code is a C program to check if a number is semiprime or not. It uses a function to check for prime numbers and then finds the two prime factors of the given number. The output displays whether the number is a semiprime or not along with its prime factors. The code's time complexity is O(number * sqrt(number)), which is acceptable for smaller values of 'number.' However, for larger numbers, the execution time may increase significantly.
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