Skip to main content

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.

  1. First, we check if 77 is a semiprime by finding its prime factors.
  2. Start iterating through numbers from 2 to 77/2, which is up to 38 in this case.
  3. For each number, we check if it is a prime number using the 'is_prime' function.
  4. If the number is both prime and divides 77 evenly (77 % i == 0), then we have found one of the prime factors.
  5. We store the first prime factor in the variable 'first.'
  6. As we continue the iteration, we find the second prime factor and store it in the variable 'second.'
  7. 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

  1. Define the 'is_prime' function to check whether a given number is prime or not.
  2. Initialize 'first' and 'second' variables to store the two prime factors of the number.
  3. Iterate through numbers from 2 to number/2.
  4. For each number, check if it is a prime number using the 'is_prime' function.
  5. 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.
  6. 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:

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

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

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

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

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