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 notint 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 notbool 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 numberbool isChenPrime(int n){ if (isPrime(n) && (isSemiprime(n + 2) || isPrime(n + 2))) return true; else return false;}// Driver codeint main(){ int n = 7; if (isChenPrime(n)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// JAVA program to check// Chen Prime numberclass 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 numberusing 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 numberimport 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 coden = 7if(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 notfunction 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 notfunction 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 numberfunction isChenPrime(n){ if (isPrime(n) && (isSemiprime(n + 2) || isPrime(n + 2))) return true; else return false;}// Driver codevar 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
