Enlightened Number is a composite number N if it begins with the concatenation of its distinct prime factors
Some Enlightened numbers are:
250, 256, 2048, 2176, 2304, 2500, 2560…
Check if N is an Enlightened number
Given a number N, the task is to check if N is an Enlightened Number or not. If N is an Enlightened Number then print “Yes” else print “No”.
Examples:
Input: N = 2500
Output: Yes
Explanation:
factorization of 25 = 2^2 * 5^4
and N begins also with ’25’.
Input: N = 25
Output: No
Approach: The idea is to check if N is composite or not, If not composite return false otherwise concatenate all the distinct prime factors of the number N in a string. Also, convert the number N to string. Now we just have to check if the concatenation of distinct prime factors is a prefix of the number N or not, If it is then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ implementation of the // above approach #include<iostream>#include<math.h>using namespace std;// Function to check if N is a // Composite Number bool isComposite(int n) { // Corner cases if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Function to return concatenation of // distinct prime factors of a given number n int concatenatePrimeFactors(int n) { char concatenate; // Handle prime factor 2 explicitly // so that can optimally handle // other prime factors. if (n % 2 == 0) { concatenate += char(2); while (n % 2 == 0) n = n / 2; } // n must be odd at this point. // So we can skip one element // (Note i = i + 2) for(int i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, print // i and divide n if (n % i == 0) { concatenate += i; while (n % i == 0) n = n / i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) concatenate += n; return concatenate; } // Function to check if a number is // is an enlightened number bool isEnlightened(int N) { // Number should not be prime if (!isComposite(N)) return false; // Converting N to string char num = char(N); // Function call char prefixConc = concatenatePrimeFactors(N); return int(prefixConc); } // Driver code int main() { int n = 250; if (isEnlightened(n)) cout << "Yes"; else cout << "No"; } // This code is contributed by adityakumar27200 |
Java
// Java implementation of the// above approachimport java.util.*;class GFG { // Function to check if N is a // Composite Number static boolean isComposite(int n) { // Corner cases if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Function to return concatenation of // distinct prime factors of a given number n static String concatenatePrimeFactors(int n) { String concatenate = ""; // Handle prime factor 2 explicitly // so that can optimally handle // other prime factors. if (n % 2 == 0) { concatenate += "2"; while (n % 2 == 0) n = n / 2; } // n must be odd at this point. // So we can skip one element // (Note i = i + 2) for (int i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n, print // i and divide n if (n % i == 0) { concatenate += i; while (n % i == 0) n = n / i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) concatenate += n; return concatenate; } // Function to check if a number is // is an enlightened number static boolean isEnlightened(int N) { // number should not be prime if (!isComposite(N)) return false; // converting N to string String num = String.valueOf(N); // function call String prefixConc = concatenatePrimeFactors(N); return num.startsWith(prefixConc); } // Driver code public static void main(String args[]) { int n = 250; if (isEnlightened(n)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
# Python3 implementation of the # above approach import math# Function to check if N is a # Composite Number def isComposite(n): # Corner cases if n <= 3: return False # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return True i = 5 while(i * i <= n): if(n % i == 0 or n % (i + 2) == 0): return True i = i + 6 return False# Function to return concatenation of # distinct prime factors of a given number n def concatenatePrimeFactors(n): concatenate = "" # Handle prime factor 2 explicitly # so that can optimally handle # other prime factors. if(n % 2 == 0): concatenate += "2" while(n % 2 == 0): n = int(n / 2) # n must be odd at this point. # So we can skip one element # (Note i = i + 2) i = 3 while(i <= int(math.sqrt(n))): # While i divides n, print # i and divide n if(n % i == 0): concatenate += str(i) while(n % i == 0): n = int(n / i) i = i + 2 # This condition is to handle the # case when n is a prime number # greater than 2 if(n > 2): concatenate += str(n) return concatenate# Function to check if a number is # is an enlightened number def isEnlightened(N): # Number should not be prime if(not isComposite(N)): return False # Converting N to string num = str(N) # Function call prefixConc = concatenatePrimeFactors(N) return int(prefixConc)# Driver code if __name__=="__main__": n = 250 if(isEnlightened(n)): print("Yes") else: print("No")# This code is contributed by adityakumar27200 |
C#
// C# implementation of the// above approachusing System;class GFG{// Function to check if N is a// Composite Numberstatic bool isComposite(int n){ // Corner cases if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for(int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to return concatenation of// distinct prime factors of a given number nstatic String concatenatePrimeFactors(int n){ String concatenate = ""; // Handle prime factor 2 explicitly // so that can optimally handle // other prime factors. if (n % 2 == 0) { concatenate += "2"; while (n % 2 == 0) n = n / 2; } // n must be odd at this point. // So we can skip one element // (Note i = i + 2) for(int i = 3; i <= Math.Sqrt(n); i = i + 2) { // While i divides n, print // i and divide n if (n % i == 0) { concatenate += i; while (n % i == 0) n = n / i; } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) concatenate += n; return concatenate;}// Function to check if a number is// is an enlightened numberstatic bool isEnlightened(int N){ // Number should not be prime if (!isComposite(N)) return false; // Converting N to string String num = String.Join("", N); // Function call String prefixConc = concatenatePrimeFactors(N); return num.StartsWith(prefixConc);}// Driver codepublic static void Main(String []args){ int n = 250; if (isEnlightened(n)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the // above approach // Function to check if N is a // Composite Number function isComposite(n) { // Corner cases if (n <= 3) return false; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return true; for(var i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false; } // Function to return concatenation of // distinct prime factors of a given number n function concatenatePrimeFactors(n) { var concatenate; // Handle prime factor 2 explicitly // so that can optimally handle // other prime factors. if (n % 2 == 0) { concatenate += "2"; while (n % 2 == 0) n = parseInt(n / 2); } // n must be odd at this point. // So we can skip one element // (Note i = i + 2) for(var i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n, print // i and divide n if (n % i == 0) { concatenate += i; while (n % i == 0) n = parseInt(n / i); } } // This condition is to handle the // case when n is a prime number // greater than 2 if (n > 2) concatenate += n; return concatenate; } // Function to check if a number is // is an enlightened number function isEnlightened(N) { // Number should not be prime if (!isComposite(N)) return false; // Converting N to string var num = (N.toString()); // Function call var prefixConc = concatenatePrimeFactors(N); return (prefixConc); } // Driver code var n = 250; if (isEnlightened(n)) document.write( "Yes"); else document.write( "No"); </script> |
Output:
Yes
Time Complexity: O(n)
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!
Share your thoughts in the comments
