Brilliant Number is a number N which is the product of two primes with the same number of digits.
Few Brilliant numbers are:
4, 6, 9, 10, 14, 15, 21, 25, 35, 49….
Check if N is a Brilliant number
Given a number N, the task is to check if N is a Brilliant Number or not. If N is a Brilliant Number then print “Yes” else print “No”.
Examples:
Input: N = 1711
Output: Yes
Explanation:
1711 = 29*59 and both 29 and 59 have two digits.
Input: N = 16
Output: No
Approach: The idea is to find all the primes less than or equal to the given number N using Sieve of Eratosthenes. Once we have an array that tells all primes, we can traverse through this array to find a pair with a given product. We will find Two Prime Numbers with given product using the sieve of Eratosthenes and check if the pair has the same number of digits or not.
Below is the implementation of the above approach:
C++
// C++ implementation for the // above approach#include <bits/stdc++.h>using namespace std;// Function to generate all prime// numbers less than nbool SieveOfEratosthenes(int n, bool isPrime[]){ // Initialize all entries of // boolean array as true. // A value in isPrime[i] // will finally be false // if i is Not a prime isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) isPrime[i] = true; for (int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) isPrime[i] = false; } }}// Function to return the number// of digits in a numberint countDigit(long long n){ return floor(log10(n) + 1);}// Function to check if N is a// Brilliant numberbool isBrilliant(int n){ int flag = 0; // Generating primes using Sieve bool isPrime[n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers // to find first pair for (int i = 2; i < n; i++) { int x = n / i; if (isPrime[i] && isPrime[x] and x * i == n) { if (countDigit(i) == countDigit(x)) return true; } } return false;}// Driver Codeint main(){ // Given Number int n = 1711; // Function Call if (isBrilliant(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation for the // above approachimport java.util.*;class GFG{// Function to generate all prime// numbers less than nstatic void SieveOfEratosthenes(int n, boolean isPrime[]){ // Initialize all entries of // boolean array as true. // A value in isPrime[i] // will finally be false // if i is Not a prime isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; i++) isPrime[i] = true; for (int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) isPrime[i] = false; } }}// Function to return the number// of digits in a numberstatic int countDigit(int n){ int count = 0; while (n != 0) { n = n / 10; ++count; } return count;}// Function to check if N is a// Brilliant numberstatic boolean isBrilliant(int n){ int flag = 0; // Generating primes using Sieve boolean isPrime[] = new boolean[n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers // to find first pair for (int i = 2; i < n; i++) { int x = n / i; if (isPrime[i] && isPrime[x] && (x * i) == n) { if (countDigit(i) == countDigit(x)) return true; } } return false;}// Driver Codepublic static void main (String[] args){ // Given Number int n = 1711; // Function Call if (isBrilliant(n)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by Ritik Bansal |
Python3
# Python3 program for the # above approachimport math# Function to generate all prime # numbers less than n def SieveOfEratosthenes(n, isPrime): # Initialize all entries of # boolean array as true. # A value in isPrime[i] # will finally be false # if i is Not a prime isPrime[0] = isPrime[1] = False for i in range(2, n + 1, 1): isPrime[i] = True p = 2 while(p * p <= n ): # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] == True): # Update all multiples of p for i in range(p * 2, n + 1, p): isPrime[i] = False p += 1 # Function to return the number # of digits in a number def countDigit(n): return math.floor(math.log10(n) + 1) # Function to check if N is a # Brilliant number def isBrilliant(n): flag = 0 # Generating primes using Sieve isPrime = [0] * (n + 1) SieveOfEratosthenes(n, isPrime) # Traversing all numbers # to find first pair for i in range(2, n, 1): x = n // i if (isPrime[i] and isPrime[x] and x * i == n): if (countDigit(i) == countDigit(x)): return True return False # Driver Code # Given Number n = 1711 # Function Call if (isBrilliant(n)): print("Yes") else: print("No") # This code is contributed by sanjoy_62 |
C#
// C# implementation for the // above approachusing System;class GFG{// Function to generate all prime// numbers less than nstatic void SieveOfEratosthenes(int n, bool []isPrime){ // Initialize all entries of // boolean array as true. // A value in isPrime[i] // will finally be false // if i is Not a prime isPrime[0] = isPrime[1] = false; for(int i = 2; i <= n; i++) isPrime[i] = true; for(int p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for(int i = p * 2; i <= n; i += p) isPrime[i] = false; } }}// Function to return the number// of digits in a numberstatic int countDigit(int n){ int count = 0; while (n != 0) { n = n / 10; ++count; } return count;}// Function to check if N is a// Brilliant numberstatic bool isBrilliant(int n){ //int flag = 0; // Generating primes using Sieve bool []isPrime = new bool[n + 1]; SieveOfEratosthenes(n, isPrime); // Traversing all numbers // to find first pair for(int i = 2; i < n; i++) { int x = n / i; if (isPrime[i] && isPrime[x] && (x * i) == n) { if (countDigit(i) == countDigit(x)) return true; } } return false;}// Driver Codepublic static void Main(){ // Given Number int n = 1711; // Function Call if (isBrilliant(n)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation for the // above approach // Function to generate all prime // numbers less than n function SieveOfEratosthenes( n, isPrime) { // Initialize all entries of // let array as true. // A value in isPrime[i] // will finally be false // if i is Not a prime isPrime[0] = isPrime[1] = false; for ( let i = 2; i <= n; i++) isPrime[i] = true; for (let p = 2; p * p <= n; p++) { // If isPrime[p] is not changed, // then it is a prime if (isPrime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) isPrime[i] = false; } } } // Function to return the number // of digits in a number function countDigit( n) { let count = 0; while (n != 0) { n = parseInt(n / 10); ++count; } return count; } // Function to check if N is a // Brilliant number function isBrilliant( n) { let flag = 0; // Generating primes using Sieve let isPrime = Array(n + 1).fill(true); SieveOfEratosthenes(n, isPrime); // Traversing all numbers // to find first pair for ( let i = 2; i < n; i++) { let x = n / i; if (isPrime[i] && isPrime[x] && (x * i) == n) { if (countDigit(i) == countDigit(x)) return true; } } return false; } // Driver Code // Given Number let n = 1711; // Function Call if (isBrilliant(n)) document.write("Yes"); else document.write("No");// This code contributed by Rajput-Ji</script> |
Output:
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
Reference: http://oeis.org/A078972
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!
