Chen Prime Number

0 0 6 minutes read

Given a positive integer n, the task is to check if it is a Chen prime number. If the given number is a Chen Prime number then print ‘YES’ otherwise print ‘NO’.
Chen prime Number: In mathematics, a Prime number ‘p’ is called as chen prime number , if either ‘p+2’ is a prime number or a semi prime number.
A semi-prime number is product of two prime numbers.
The first few Chen prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89, 101

Examples:

Input : 11
Output: YES
Explanation:
11 is prime number and 11+2
(i.e 13 is also prime number)

Input : 7
Output: YES
Explanation:
7 is prime number and 7+2
( i.e 9 ) is a semi prime number

Prerequisite:

Approach:

Check if the given number – ‘n’ is a prime or not.
If n is a prime number:
- Check if n+2 is either prime or semi-prime
- Print ‘YES’ if n+2 is either prime number or a semi-prime number
- Otherwise print ‘NO’
If n is not a prime number, print ‘NO’.

Below is the implementation of the above idea

CPP

// CPP program to check
// Chen prime number
 
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to check whether
// number is semiprime or not
int isSemiprime(int num)
{
    int cnt = 0;
 
    for (int i = 2; cnt < 2 && i * i <= num; ++i)
        while (num % i == 0)
            num /= i, ++cnt; // Increment count
    // of prime numbers
 
    // If number is greater than 1, add it to
    // the count variable as it indicates the
    // number remain is prime number
    if (num > 1)
        ++cnt;
 
    // Return '1' if count is equal to '2' else
    // return '0'
    return cnt == 2;
}
 
// Utility function to check whether
// the given number is prime or not
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}
 
// Function to check Chen prime number
bool isChenPrime(int n)
{
 
    if (isPrime(n) && (isSemiprime(n + 2) || isPrime(n + 2)))
        return true;
    else
        return false;
}
 
// Driver code
int main()
{
    int n = 7;
 
    if (isChenPrime(n))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

Java

// JAVA program to check
// Chen Prime number
 
class GFG {
    // Utility function to check
    // if the given number is semi-prime or not
    static boolean isSemiPrime(int num)
    {
        int cnt = 0;
 
        for (int i = 2; cnt < 2 && i * i <= num; ++i)
 
            while (num % i == 0) {
                num /= i;
 
                // Increment count
                // of prime numbers
                ++cnt;
            }
 
        // If number is greater than 1,
        // add it to the count variable
        // as it indicates the number
        // remain is prime number
        if (num > 1)
            ++cnt;
 
        // Return '1' if count is equal
        // to '2' else return '0'
        return cnt == 2 ? true : false;
    }
 
    // Function to check if a number is prime or not
    static boolean isPrime(int n)
    {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // Function to check chen prime number
    static boolean isChenPrime(int n)
    {
 
        if (isPrime(n) && (isSemiPrime(n + 2) || isPrime(n + 2)))
            return true;
        else
            return false;
    }
    // Driver code
    public static void main(String[] args)
    {
 
        int n = 7;
 
        if (isChenPrime(n))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

C#

// C# program to check
// Chen Prime number
using System;
class GFG {
    // Utility function to check
    // if the given number is semi-prime or not
    static bool isSemiPrime(int num)
    {
        int cnt = 0;
 
        for (int i = 2; cnt < 2 && i * i <= num; ++i)
 
            while (num % i == 0) {
                num /= i;
 
                // Increment count
                // of prime numbers
                ++cnt;
            }
 
        // If number is greater than 1,
        // add it to the count variable
        // as it indicates the number
        // remain is prime number
        if (num > 1)
            ++cnt;
 
        // Return '1' if count is equal
        // to '2' else return '0'
        return cnt == 2 ? true : false;
    }
 
    // Function to check if a number is prime or not
    static bool isPrime(int n)
    {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // Function to check chen prime number
    static bool isChenPrime(int n)
    {
 
        if (isPrime(n) && (isSemiPrime(n + 2) || isPrime(n + 2)))
            return true;
        else
            return false;
    }
    // Driver code
    public static void Main()
    {
 
        int n = 7;
 
        if (isChenPrime(n))
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}

Python3

# Python3 program to check
# Chen Prime number
 
import math
         
# Utility function to Check 
# Semi-prime number 
 
def isSemiPrime(num): 
    cnt = 0
   
    for i in range(2, int(math.sqrt(num)) + 1): 
        while num % i == 0: 
            num /= i 
            cnt += 1 # Increment count 
                    # of prime number 
   
        # If count is greater than 2, 
        # break loop  
        if cnt >= 2:  
            break
    # If number is greater than 1, add it to 
    # the count variable as it indicates the 
    # number remain is prime number 
    if(num > 1): 
        cnt += 1
   
    # Return '1' if count is equal to '2' else 
    # return '0' 
    return cnt == 2
  
  
 
# Utility function to check  
# if a number is prime or not  
def isPrime(n) :   
    # Corner cases   
    if (n <= 1) :   
        return False
    if (n <= 3) :   
        return True
     
    # This is checked so that we can skip   
    # middle five numbers in below loop   
    if (n % 2 == 0 or n % 3 == 0) :   
        return False
     
    i = 5
    while(i * i <= n) :   
        if (n % i == 0 or n % (i + 2) == 0) :   
            return False
        i = i + 6
     
    return True
  
# Function to check if the
# Given number is Chen prime number or not
         
def isChenPrime( n):
 
    if(isPrime(n) and (isSemiPrime(n + 2) or isPrime(n + 2))):
        return True
    else:
        return False
             
# Driver code
 
n = 7
 
if(isChenPrime(n)):
    print("YES");
else:
    print("NO");
    

Javascript

<script>
 
// Javascript program to check
// Chen prime number
 
// Utility function to check whether
// number is semiprime or not
function isSemiprime(num)
{
    var cnt = 0;
 
    for (var i = 2; cnt < 2 && i * i <= num; ++i)
        while (num % i == 0)
            num /= i, ++cnt; // Increment count
    // of prime numbers
 
    // If number is greater than 1, add it to
    // the count variable as it indicates the
    // number remain is prime number
    if (num > 1)
        ++cnt;
 
    // Return '1' if count is equal to '2' else
    // return '0'
    return cnt == 2;
}
 
// Utility function to check whether
// the given number is prime or not
function isPrime(n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (var i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
 
    return true;
}
 
// Function to check Chen prime number
function isChenPrime(n)
{
 
    if (isPrime(n) && (isSemiprime(n + 2) || isPrime(n + 2)))
        return true;
    else
        return false;
}
 
// Driver code
var n = 7;
if (isChenPrime(n))
    document.write( "YES");
else
    document.write( "NO");
 
// This code is contributed by noob2000.
</script>

Output:

YES

Time Complexity: O(?n)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!